洛谷 P4391 [BOI2009]Radio Transmission 无线传输 题解【KMP】【字符串】

点击量：192

    一道比较简单的利用nxt数组的题。

目录

题目描述

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

 

输入输出格式

输入格式：

第一行给出字符串的长度，\(1<L\le 1,000,000\)。

 

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

 

输出格式：

输出最短的长度。

 

输入输出样例

输入样例#1：

8
cabcabca

输出样例#1：

3

说明

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

题解：

    这个题是要找一个循环节，使得给定的字符串可以被放进去。因为找循环节，所以一定会有非前缀后缀=前缀。如果不存在，那么只能整个字符串为一个循环节。而答案最大为\(n\)，一旦存在非前缀后缀=前缀，那么答案就会减小，可以把前面和后面“粘在一起”。

    而只要找到了最长的非后缀前缀=后缀的长度\(l\)，答案就是\(n-l\)。而求最长非后缀前缀是KMP做的事，而这里的答案和nxt[n]有关。因此顺着KMP求nxt数组的思路，求出nxt[n]。接着可以发现nxt数组就是符合条件的长度，那么答案就是\(n-nxt[n]\)。

    这篇题解甚至是题目貌似有点水，但是思路很重要……

Code：

#include<cstdio>
#include<cstring>
int nxt[1001000];
char s[1001000];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=2,j=0;i<=n;++i)//求nxt数组
    {
        while(j&&s[i]!=s[j+1])
            j=nxt[j];
        if(s[j+1]==s[i])
            ++j;
        nxt[i]=j;
    }
    printf("%d\n",n-nxt[n]);//输出答案
    return 0;
}