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

作者: wjyyy 分类: KMP,字符串,解题报告 发布时间: 2018-09-13 17:50

点击量:9

 

    一道比较简单的利用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;
}

说点什么

avatar
  Subscribe  
提醒
/* */