正文
HUST 1328 String
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
11:
KMP next 的强大
题意求前缀在S中出现的次数之和
next[j] 表示 S[0....NEXT[J]]==S[J-NEXT[J].....J];
于是我们得到。。后加入一个字符所得到新的前缀会多ADD[next[J]]个
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
#define N 123456
char s[N];
int next[N];
int n;
ll a[N];
void kmp()
{
n=strlen(s);
int i=0,j=-1;
next[0]=-1;
while (i<n)
{
if (j==-1||s[i]==s[j])
{
i++;
j++;
next[i]=j;
}else j=next[j];
}
}
int main()
{
while (scanf("%s",s)!=EOF)
{
kmp();
ll ans=0;
memset(a,0,sizeof(a));
for (int i=1;i<=n;i++)
{
a[i]=a[next[i]];
a[i]++;
ans+=a[i];
}
printf("%lld\n",ans);
}
return 0;
}
