KMP POJ 2406 Power Strings

题目传送门

 /*

     题意：一个串有字串重复n次产生，求最大的n

     KMP：nex[]的性质应用，感觉对nex加深了理解

 */

 /************************************************

 * Author        :Running_Time

 * Created Time  :2015-8-10 10:51:54

 * File Name     :POJ_2406.cpp

  ************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 typedef long long ll;

 const int MAXN = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 char str[MAXN];

 int nex[MAXN];

 int get_nex(void)   {

     int len = strlen (str);

     int i = , j = -;  nex[] = -;

     while (i < len) {

         if (j == - || str[j] == str[i])    {

             j++;    i++;    nex[i] = j;

         }

         else    j = nex[j];

     }

     if (i % (i - nex[i]) == )  {

         return i / (i - nex[i]);

     }

     else    return ;

 }

 int main(void)    {     //POJ 2406 Power Strings

     while (scanf ("%s", str) == )  {

         if (str[] == '.')  break;

         printf ("%d\n", get_nex ());

     }

     return ;

 }