锐客网

  1. 首页 > it技术 > >

poj 2406 Power Strings kmp算法

此题用KMP算法做是最简单的，代码也很短。

#include #include char ch[1000005]; int f[1000005]; int main() { int i,j,k; while(scanf("%s",ch)!=-1&&ch[0]!='.') { int m=strlen(ch); for(i=1; i

另外附上滔神的代码，快速读入，优化到32ms

#include #includeint next[1111111] ; void get_next ( char *s , int n ) { int i , j ; j = -1 ; next[0] = -1 ; for ( i = 1 ; i < n ; i ++ ) { while ( j > -1 && s[j+1] != s[i] ) j = next[j] ; if ( s[j+1] == s[i] ) j ++ ; next[i] = j ; } }char s[1111111] ; int main () { int n , k ; n = 0 ; while ( s[n++] = getchar () ) { while ( ( s[n++] = getchar () ) != 10 ) ; n -- ; if ( n == 1 && s[0] == '.' ) break ; get_next ( s , n ) ; k = next[n-1] ; if ( n % ( n - 1 - k ) ) puts ( "1" ) ; else printf ( "%d\n" , n / ( n - 1 - k ) ) ; n = 0 ; } }




【poj 2406 Power Strings kmp算法】

    推荐阅读


    上一篇：ATX ATX-uiautomator2 使用 QPython 在 Android 手机内执行自动化

    下一篇：SAS宏技术中,%let和call symput有什么区别（）