HDU 3336 扩展kmp

时间：2023-03-08 20:45:42

题目大意：

找到字符串中所有和前缀字符串相同的子串的个数

对于这种前缀的问题，通常通过扩展kmp来解决

其实吧这是我第一次做扩展kmp的题目，原来确实看过这个概念，今天突然做到，所以这个扩展kmp的模板是做到这道题直接copy的

这里用扩展kmp很好解决问题,_next[i]，表示第i位开始所能匹配到的最大公共前缀长度，比如说这个长度为4，那么说明前缀1,2,3,4都出现了一次，我们只在cnt[4]++

那么最后从n到1，逆向更新cnt[i] += cnt[i+1]即可，最后得到cnt[i]就表示前缀长度为i的时候所能得到的相同的子串的个数

 #include <cstdio>

 #include <iostream>

 #include <cstring>

 using namespace std;

 #define N 200005

 #define MOD 10007

 char s[N];

 int _next[N] , cnt[N];

 void get_next(char *T){// _next[i]: 以第i位置开始的子串 与 T的公共前缀

      int i,length = strlen(T);

      _next[] = length;

      for(i = ;i<length- && T[i]==T[i+]; i++);

           _next[] = i;

           int a = ;

           for(int k = ; k < length; k++){

                   int p = a+_next[a]-, L = _next[k-a];

                   if( (k-)+L >= p ){

                        int j = (p-k+)>? (p-k+) : ;

                        while(k+j<length && T[k+j]==T[j]) j++;// 枚举(p+1，length) 与(p-k+1,length) 区间比较

                        _next[k] = j, a = k;

                   }

                   else _next[k] = L;

          }

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int T;

     scanf("%d" , &T);

     while(T--)

     {

         int n;

         scanf("%d%s" , &n , s);

         get_next(s);

       //  for(int i=0 ; i<n ; i++) cout<<_next[i]<<endl;

         memset(cnt ,  , sizeof(cnt));

         for(int i= ; i<n ; i++) cnt[_next[i]]++;

         for(int i=n- ; i>= ; i--) cnt[i]+=cnt[i+];

         int sum=;

         for(int i= ; i<=n ; i++) sum = (sum+cnt[i])%MOD;

         printf("%d\n" , sum);

     }

     return ;

 }

相关文章