HDU 3336-Count the string

川长思鸟来 2022-09-22 13:52 66阅读 0赞

HDU 3336

KMP+DP

  1. #include<cstdio>  
  2. #include<cstring>  
  3. using namespace std;  
  4. #define MAX 200005  
  5. #define mod 10007  
  6. int next[MAX],num[MAX];  
  7. char s[MAX];  
  8. void get_next()  
  9. {  
  10.     int i=0,j=-1;  
  11.     next[0]=-1;  
  12.     for(; s[i];)  
  13.         if(j==-1||s[i]==s[j])  
  14.         {  
  15.             ++i;  
  16.             ++j;  
  17.             next[i]=j;  
  18.         }  
  19.         else  j=next[j];  
  20. }  
  21. int main()  
  22. {  
  23.     int t,n;  
  24.     scanf("%d",&t);  
  25.     while(t--) 
  26.     {  
  27.         int summ=0;  
  28.         memset(num,0,sizeof(num));  
  29.         scanf("%d",&n);  
  30.         scanf("%s",s);  
  31.         get_next();  
  32.         for(int i=1;i<=n;++i)  
  33.            num[next[i]]=(num[next[i]]+1)%mod;  
  34.         for(int i=1;i<=n;++i)  
  35.            if(num[i])  
  36.               summ=(summ+num[i]+1)%mod;  
  37.             else  
  38.               summ=(summ+1)%mod;  
  39.         printf("%d\n",summ);  
  40.     }  
  41.     return 0;  
  42. }

发表评论

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

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

相关阅读