HDU 1358 Period KMP-白红宇

HDU 1358 Period KMP

阅读量：5157 次

发布时间：2019-06-13

本文共 1279 字，大约阅读时间需要 4 分钟。

题意：求一个字符串的所有前缀是否是复制出来的。

解题思路：next 数值判断即可

解题代码：

1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4  5 #include
      
        6 #include
       
         7 #include
         8 #include
         
           9 #include
          
           10 #include
           
            11 #include
            
             12 #include
             
              13 #include
              
               14 #include
               
                15 #include
                
                 16 #include
                 
                  17 #include
                  
                   18 #include
                   
                    19 #include
                    
                     20 #include
                     
                      21 #include
                      
                       22 #include
                       
                        23 #include
                        
                         24 #define LL long long25 26 using namespace std;27 char str[1000004];28 int next[1000005];29 void getnext()30 {31 int len = strlen(str);32 next[0] = -1; 33 int k = -1;34 int j = 0 ;35 int sum = 0 ; 36 while(j <= len - 1)37 {38 if(k == -1 || str[j] == str[k])39 {40 ++j; 41 ++k;42 next[j] = k ;43 }44 else {45 k = next[k];46 }47 }48 /* for(int i = 0 ;i <= len; i ++)49 printf("%d ",next[i]);50 printf("\n");*/51 for(int i = 2;i <=len; i ++)52 {53 int t = (i - next[i]);54 if(i % t == 0 && i /t != 1)55 {56 printf("%d %d\n",i,i/t); 57 }58 }59 60 }61 int main(){62 int n ;63 int t = 0 ;64 while(scanf("%d",&n) != EOF,n)65 {66 t++ ;67 scanf("%s",str);68 printf("Test case #%d\n",t);69 getnext();70 printf("\n"); 71 }72 return 0;73 }