HDU 1358(kmp)

叁歲伎倆 2022-09-20 12:44 124阅读 0赞

题意：给出一个数字n，接下来一行是一个字符串，n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。

kmp中的next数组只得是第i个字符匹配错误，向前跳的位置next【i】。

  1. #include<algorithm>
  2. #include<stdio.h>
  3. #include<string>
  4. #include<string.h>
  5. #include<math.h>
  6. #include<queue>
  7. #include<iostream>
  8. using namespace std;
  10. int i,j,k;
  12. int len;
  14. char s[1000001];
  16. int next[1000001];
  18. void get_next()  
  19. {  
  20.     int i=0,j=-1;  
  21.     next[0]=-1;  
  22.     for(;s[i];)  
  23.         if(j==-1||s[i]==s[j])  
  24.         {  
  25.             ++i;++j;  
  26.             next[i]=j;  
  27.         }  
  28.         else j=next[j];  
  29. }  
  32. int main(){
  34. int t=1;
  36.     while(scanf("%d",&len)&&len){
  38.         getchar();
  40.         scanf("%s",s);
  42.         get_next();
  44.         printf("Test case #%d\n",t++);
  46.         for(i=2;i<=len;i++){
  48.              j=i-next[i];
  50.              if(i%j==0){
  52.                  if(i/j>1) printf("%d %d\n",i,i/j);
  54.             }
  56.         }
  58.         printf("\n");
  60.     }
  62.     return 0;
  64. }

发表评论

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

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

相关阅读

    相关 HDU 1358(kmp)

    题意：给出一个数字n，接下来一行是一个字符串，n是这个字符串的长度。求这个字符串的所有是循环字符串的前缀。 kmp中的next数组只得是第i个字符匹配错误，向前跳的位置nex

    叁歲伎倆叁歲伎倆/ 0 赞/ 125 阅读