2020-11-14

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

输入格式

输入若干行，每行有一个字符串。特别的，字符串可能为 . 即一个半角句号，此时输入结束。

样例

样例输入

abcd

aaaa

ababab

.

样例输出

1

4

3

数据范围与提示

字符串长度 ≤10^6。

题意：给出字符串，求解字符串由几个子串重复而成，利用kmp求出next数组，然后通过(l%nex[l]==0&&nex[l]!=0)

来判断字符串是否为循环串，如果不是，那就有它自身组成，输出1，如果是，求出循环子串长度（l-nex[l]）,然后

用总长度l除以循环子串长度（l-nex[l]）得出字符串有几个子串，即有l/(l-nex[l])个子串。

代码：

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+10;
int nex[M];///next数组，存储字符串最大公共前后缀长度
char a[M];///字符串
///求next数组
void getnext(int l)
{
    int i=0,j=-1;
    nex[0]=-1;
    while(i<l)
    {
        if(j==-1||a[i]==a[j])
        {
            i++;
            j++;
            nex[i]=j;
        }
        else
            j=nex[j];
    }
}
int main()
{

    while(~scanf("%s",a))
    {
        if(a[0]=='.')///字符为 . 时停止程序
            break;
        int i,j,k,l,m,n,s=0;
        l=strlen(a);
        getnext(l);
        ///当(l%nex[l]==0&&nex[l]!=0)
        ///字符串为某个子串循环而成
        ///l-nex[l]为循环子串长度
        ///l/nex[l]为循环次数，即字符串由几个子串循环而成
        if(l%(l-nex[l]))
            printf("1\n");
        else
            printf("%d\n",l/(l-nex[l]));
    }

    return 0;
}