P4391 [BOI2009]Radio Transmission 无线传输(KMP)

题目描述

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少.

输入输出格式

输入格式：

第一行给出字符串的长度,1 < L ≤ 1,000,000.

第二行给出一个字符串，全由小写字母组成.

输出格式：

输出最短的长度

输入输出样例

输入样例#1：

8

cabcabca

输出样例#1：
3

说明

对于样例,我们可以利用"abc"不断自我连接得到"abcabcabc",读入的cabcabca,是它的子串.

求一下kmp的前缀数组，不难发现，前几项都是0后面是1 2 3 ...所以有 len-p[len]为得数

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

#include<queue>

#include<set>

#include<map>

#include<ctime>

using namespace std;

const int maxn =  +  ;

int p[maxn];

char A[maxn];

int main()

{

    int len;

    cin>>len;

    scanf("%s",A+);

    p[]=;

    int j();

    for(int i=;i<len;i++)

    {

        while(j && A[i+]!=A[j+]) j=p[j];

        if(A[j+]==A[i+]) j++;

        p[i+]=j;

    }

    cout<<len-p[len]<<endl;

    return ;

}

巴特西