【题解】洛谷P4391 [BOI2009] Radio Transmission（KMP）

洛谷P4391：https://www.luogu.org/problemnew/show/P4391

思路

对于给定的字符串 运用KMP思想

设P[x]为前x个字符前缀和后缀相同的最长长度

则对于题目中的长度len有：

len-p[len]为第一个重复子串的最后一个字符位置

因此len-p[len]即重复子串长度

证明：

因为p[len]为前len个字符中前缀和后缀相同的最长长度

先对于一个重复串来观察

abcd abcd abcd

则对于p[12]=8 就是它后面多出来的重复串

用总长把多出来的重复串减去即可得到原始重复串的长度

通过题目已经知道原串是一条自重复串

那么不妨设x为原始重复串的长度 则x+1到len都是他重复的部分

因此我们求出p[len]就是后面重复部分的长度

则len-p[len]就满足原始重复串的长度

模拟样例：

字符串：c a b c a b c a

对应P： 0 0 0 1 2 3 4 5

则len-p[len]的位置为3

因为1~5的cabca与4~8的cabca相同

对于4~8的字符串都是原始字符串的重复部分

所以只要再补上一个b

即可满足重复串cabcabcab

代码

#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define maxn 1000010 char a[maxn]; int p[maxn]; int len,j; int main() { scanf("%d",&len); scanf("%s",a+1); for(int i=2;i<=len;i++)//常规KMP求P数组 { while(j&&a[j+1]!=a[i]) j=p[j]; if(a[j+1]==a[i]) j++; p[i]=j; } printf("%d",len-p[len]);//输出原始重复串长度 }

转载于:https://www.cnblogs.com/BrokenString/p/9781626.html

相关资源：JAVA上百实例源码以及开源项目