English题面

题意：

给你一个长度为n的字符串，依次取字符串前i个（前缀），如果前缀由k(k>0)个相同真子串构成，那么输出i和k

直到n为0结束，每组数据后要有一行空白

思路：

KMP+一点点判断

其实这道题并不是很难

可以先用KMP求出最长的 是s[1~i]的前缀和后缀的真子串的长度j

话说的有点复杂，分开来理

1、真子串：

不是字符串本身的子串

2、是s[1~i]的前缀和后缀：

以aabaab为例

aabaab

aabaab

aab是aabaab的前缀，又是后缀

j=3

两种条件下：

以aaa为例

就应该是

aaa

aaa

aa是aaa的前缀&后缀&真子串

j=2

判断方法

if(i%(i-j)==0) //说明循环的子串长度为i-j，循环次数为i/(i-j)

证明：

RT：

$\because$ l=r

$\therefore$ ①=①，②=②，③=③

$\therefore$ ①=②=③

其他情况无论多少都可以这样 连等，只要i-j能够整除i那么就是成立的

Code：

#include<bits/stdc++.h>
using namespace std;
string s;
int n,t;
int len,cur;
int p[1000010];
int read()
{
    int s=0;
    char c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c))
    {
        s=(s<<1)+(s<<3)+c-'0';
        c=getchar();
    }
    return s;
}
int main()
{
    int i,j;
    n=read();
    while(n)
    {
        printf("Test case #%d\n",++t);
        cin>>s;
        len=s.size();
        for(i=len;i;i--)
            s[i]=s[i-1];
        for(i=2,j=0;i<=len;i++)//KMP大法
        {
            while(j&&s[i]!=s[j+1])//求前缀的那个东东
                j=p[j];
            if(s[i]==s[j+1])
                j++;
            p[i]=j;
            if(j>=(i>>1)&&i%(i-j)==0)//判断一下
                printf("%d %d\n",i,i/(i-j));
        }
        printf("\n");
        n=read();
    }
    return 0;
}

友情链接

KMP百度百科

【模板】KMP字符串匹配

devil.