【kmp】似乎在梦中见过的样子

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 
 5 using namespace std;
 6 const int N = 1e5+10;
 7 
 8 char s[N];
 9 int k,n,ans;
10 int Next[N];
11 int main()
12 {
13     scanf("%s%d",s+1,&k);
14     n = strlen( s+1 );
15 
16     //printf("%s %d %d\n",s+1,k,n);
17     //枚举所有合法的左端点,左端点 预留2*k的距离
18     for(int L=1; L<= n-(k*2) ; L++ ) {
19 
20         for(int i = 1 ; i <= L ; i++ ) Next[i] = L-1 ;
21 
22         //提前预处理好Next数组
23         for(int i=L+1,j=L-1;i<=n;i++){
24             while( j != L-1 && s[i] != s[j+1] ) j=Next[j];
25             if( s[i] == s[j+1] ) j++ ;
26             Next[i] = j ;
27         }
28 
29         for(int i=L+1,j=L-1;i<=n;i++){
30             while( j != L-1 && s[i] != s[j+1] ) j=Next[j];
31             if( s[i] == s[j+1] ) j++ ;
32 
33             //预处理的Next派上用场了
34             //当最长前缀的两倍 > 当前串(右端点-左端点)的长度
35             //利用Next数组缩短距离
36             while( (j-L+1)*2 >= (i-L+1) ) j = Next[j] ;
37 
38             //符合题意 累加答案，即前缀长度大于k
39             if( j-L+1 >= k ) ans ++ ;
40         }
41 
42     }
43     printf("%d\n",ans);
44     return 0;
45 }