Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a (a^n).
链接 POJ-2406
题解 写了个后缀数组水过，还是说正解吧
代码 后缀数组就不附了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <cstdio> #include <cstring> #include <cstdlib> #include <vector> #include <algorithm> #include <cmath> #include <cctype> #include <iostream> using namespace std ;const int MAXN = 1000010 ;char T[MAXN << 1 ], P[MAXN];int next[MAXN];inline void getNext (int m) register int i = 0 , j = -1 ; next[0 ] = -1 ; while (i < m) { if (j == -1 || P[i] == P[j]) { i++, j++; if (P[i] != P[j])next[i] = j; else next[i] = next[j]; } else j = next[j]; } } inline int kmp (int pos, int n, int m) register int i = pos, j = 0 ; while (i < n && j < m) { if (j == -1 || T[i] == P[j]) i++, j++; else j = next[j]; } if (j == m) return i - m; else return -1 ; } int main () while (scanf ("%s" , P), P[0 ] != '.' ) { register int n, m; m = strlen (P), n = m << 1 ; strcpy (T, P), strcpy (T + m, P), getNext(m); printf ("%d\n" , m / kmp(1 , n, m)); } return 0 ; }
