题目链接：https://www.luogu.com.cn/problem/SP694
题意
- t组测试样例，每组给一个字符串
- 求该字符串本质不同的子串的个数
- 子串其实就是字符串后缀的前缀。比如给一个串是“abaab”，则"aa"是后缀“aab”的前缀。
- 要算前缀种数，就要马上想到字典树啦，它可以很方便的求出字符串前缀的种数。
- 不过这道题把时间卡的死死的，初始化的时候要注意，还有就是字符串得定义成char类型。
#include
#define LL long long
#define sc(a) scanf("%d", &a)
#define sc2(a, b) scanf("%d%d", &a, &b)
#define sc3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define scl(a) scanf("%lld", &a)
#define scl2(a, b) scanf("%lld%lld", &a, &b)
#define ss(a) scanf("%s", a)
#define mem(a, b) memset(a, b, sizeof(a))
#define PII pair
using namespace std;
const int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
int t[maxn][127];
int tot = 1, n;
char s[maxn];
void add_node(int i, int j)
{
for (int k = j;
k < n;
k++)
{
if (!t[i][s[k]])
t[i][s[k]] = ++tot;
i = t[i][s[k]];
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
tot = 1;
ss(s);
n = strlen(s);
for (int i = 0;
i < n;
i++) //添加后缀字符串
{
add_node(1, i);
}
cout << tot - 1 << endl;
//还要减去空串
for (int i = 1;
i <= tot + 5;
i++) //数组初始化，如果直接memset会tle
for (int j = 1;
j < 127;
j++)
t[i][j] = 0;
}
system("pause");
return 0;
} 【SP694 DISUBSTR - Distinct Substrings(洛谷 字典树)】
