Hdu 3336 Count the string (KMP+DP 前缀出现次数和)

本是古典 何须时尚 2022-08-27 11:43 69阅读 0赞

题意：给一个字符串，对每一个前缀出现的次数求和。

这里有另外一种思路：【KMP】HDU 3336 Count the string - KIDxの博客 - ITeye技术网站 

  1. #include <cstdio>
  2. #include <cstring>
  4. const int MOD=10007;
  5. const int N=200005;
  6. char s[N];
  7. int next[N],n,f[N];
  9. void getNext(char s[],int len)
  10. {
  11.     next[0]=-1;
  12.     int i=0,j=-1;
  13.     while (i<len)
  14.     {
  15.         if (j==-1 || s[i]==s[j])
  16.             next[++i]=++j;
  17.         else j=next[j];
  18.     }
  19. }
  21. int DP ()
  22. {
  23.     int ans=0;
  24.     memset(f,0,sizeof(f));
  25.     for (int i=1;i<=n;i++)
  26.     {//f[i]表示长度为i的字符串(也就是把str[i]当成'\0')总共含前缀的数量
  27.         f[i]=f[next[i]]+1;//+1表示长度为next[i]的前缀在当前结尾又出现了一次
  28.         ans=(ans+f[i])%MOD;
  29.     }
  30.     return ans;
  31. }
  33. int main ()
  34. {
  35.     int T;
  36.     scanf("%d",&T);
  37.     while (T--)
  38.     {
  39.         scanf("%d",&n);
  40.         scanf("%s",s);
  41.         getNext(s,n);
  42.         printf("%d\n",DP());
  43.     }
  44.     return 0;
  45. }

发表评论

表情：
评论列表 （有 0 条评论，69人围观）

还没有评论，来说两句吧...

相关阅读