题目链接
题意
计算一个字符串与他各个后缀的最长公共前缀。
思路
扩展kmp模板题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int Next[N],extend[N];
void getNext(char str[])
{
int i=0,j,po,len=strlen(str);
Next[0]=len;
while(str[i]==str[i+1] && i+1<len) i++; Next[1]=i;
po=1;
for(i=2;i<len;i++)
{
if(Next[i-po]+i < Next[po]+po)
Next[i]=Next[i-po];
else
{
j = Next[po]+po-i;
if(j<0) j=0;
while(i+j<len && str[j]==str[j+i]) j++; Next[i]=j;
po=i;
}
}
}
void EXKMP(char s1[],char s2[])
{
int i=0,j,po,len=strlen(s1),l2=strlen(s2);
getNext(s2);
while(s1[i]==s2[i] && i<l2 && i<len) i++; extend[0]=i;
po=0;
for(i=1;i<len;i++)
{
if(Next[i-po]+i < extend[po]+po)
extend[i]=Next[i-po];
else
{
j = extend[po]+po-i;
if(j<0) j=0;
while(i+j<len && j<l2 && s1[j+i]==s2[j]) j++; extend[i]=j;
po=i;
}
}
}
char s[N];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
scanf("%s", s);
memset(extend, 0, sizeof(extend));
memset(Next, 0, sizeof(Next));
EXKMP(s, s);
ll ans = 0;
int len = strlen(s);
for (int i = 1; i < len; i++)
{
if (extend[i] < len - i)
ans += extend[i] + 1;
else
ans += extend[i];
}
printf("%lld\n", ans);
}
return 0;
}