链接：https://vjudge.net/problem/POJ-2406#author=chen_zhe_

题意：

给定若干个长度 ≤ 1000000 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有 3 个 ab 连接而成。

思路：

求kmp的next数组，next[len]对应的后缀长度可以被原长整除，则分为整除段，否则为1。

代码：

#include 
     
      #include 
      
       #include 
       
        using namespace std;const int MAXN = 1e6 + 10;int Next1[MAXN];int Next2[MAXN];void Get_Next1(char *s){    int i = 0, k = -1, len = strlen(s);    Next1[i] = k;    while (i < len)    {        if (k == -1 || s[i] == s[k])        {            i++;            k++;            Next1[i] = k;        }        else            k = Next1[k];    }}int main(){    char s[MAXN];    while (~scanf("%s", s))    {        if (s[0] == '.')            break;        Get_Next1(s);        int len = strlen(s);        int res = 1;        if (len % (len - Next1[len]) == 0)            res = len / (len - Next1[len]);        cout << res << endl;    }    return 0;}