666 专题三 KMP & 扩展KMP & Manacher
2024-09-04 15:14:37
KMP：
Problem A.Number Sequence
d.求子串首次出现在主串中的位置
s.
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 10005//字符串长度 int a[];
int b[MAXN]; int _next[MAXN]; void GetNext(int t[],int M){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
//len=strlen(t);
len=M;
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int KMPIndex(int s[],int t[],int N,int M){//求子串首次出现在主串中的位置
int i,j,lens,lent;
i=j=;
//lens=strlen(s);
//lent=strlen(t);
lens=N;
lent=M; while(i<lens&&j<lent){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=_next[j];
}
if(j>=lent)return i-lent+;
else return -;
} int main(){
int T;
int N,M; scanf("%d",&T); while(T--){
scanf("%d%d",&N,&M); for(int i=;i<N;++i){
scanf("%d",&a[i]);
}
for(int i=;i<M;++i){
scanf("%d",&b[i]);
} GetNext(b,M);
printf("%d\n",KMPIndex(a,b,N,M));
}
return ;
}
Problem B.Oulipo
d.统计子串在主串中的出现次数，可重叠
s.
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 10005//字符串长度 char W[MAXN];
char T[]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int KMPCount(char s[],char t[]){//统计子串在主串中的出现次数，可重叠
int i,j,lens,lent,cnt;
i=j=;
lens=strlen(s);
lent=strlen(t);
cnt=; while(i<lens){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=_next[j];
if(j==lent)++cnt;
}
return cnt;
} int main(){
int TT; scanf("%d",&TT); while(TT--){
scanf("%s",W);
scanf("%s",T); GetNext(W);
printf("%d\n",KMPCount(T,W));
}
return ;
}
Problem C.剪花布条
d.统计子串在主串中的出现次数，不可重叠
s.当j==lent时，直接让j=0;而不是j=_next[j];，就不重叠了~
c.
/*
kmp模板
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 1024//字符串长度 int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int KMPCount(char s[],char t[]){//统计子串在主串中的出现次数，不可重叠
int i,j,lens,lent,cnt;
i=j=;
lens=strlen(s);
lent=strlen(t);
cnt=; while(i<lens){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=_next[j];
if(j==lent){
++cnt;
j=;//不可重叠
}
}
return cnt;
} int main(){
char str1[MAXN],str2[MAXN]; while(~scanf("%s",str1)){
if(str1[]=='#')break; scanf("%s",str2);
GetNext(str2);
printf("%d\n",KMPCount(str1,str2));
}
return ;
}
Problem D.Cyclic Nacklace
d.给出一串字符串，可以在字符串的开头的结尾添加字符，求添加最少的字符，使这个字符串是循环的（例如：abcab 在结尾添加1个c变为 abcabc 既可）。
s.求出最小循环节，看总长能不能整除。
最小循环节（长度）=len-next[len];
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 100005//字符串长度 char str[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ int T;
int len;
int len2;//最小循环节长度 scanf("%d",&T); while(T--){
scanf("%s",str); GetNext(str); len=strlen(str);
len2=len-_next[len]; if(len2==len){
printf("%d\n",len2);
}
else{
if(len%len2==){
printf("%d\n",);
}
else{
printf("%d\n",len2-(len%len2));
}
}
} return ;
}
Problem E.Period
d.统计单串中从某个位置以前有多少重复的串（即判断位置i之前的串是不是循环的串。如果是，输出位置i 和循环的次数）
s.最小循环节（长度）=len-next[len];
对每个位置求出最小循环节，然后判断前面的串是不是循环的即可。
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 1000005//字符串长度 char str[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} void KMPCount2(char t[]){//统计单串中从某个位置以前有多少重复的串
int i,lent,tmp;
lent=strlen(t); for(i=;i<=lent;++i){
tmp=i-_next[i];
if(i%tmp==&&i/tmp>)
printf("\t位置：%d 个数：%d\n",i,i/tmp);
}
} int main(){ int N;
int c=;
int tmp;//最小循环节长度 while(~scanf("%d",&N)){ if(N==)break; scanf("%s",str); GetNext(str); printf("Test case #%d\n",++c);
for(int i=;i<=N;++i){
tmp=i-_next[i];
if( (i%tmp==)&&(i/tmp>) ){
printf("%d %d\n",i,i/tmp);
}
}
printf("\n");
} return ;
}
Problem F.The Minimum Length
d.最小循环节
s.
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 1000005//字符串长度 char str[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ int len;
int len2;//最小循环节长度 while(~scanf("%s",str)){
len=strlen(str);
GetNext(str);
len2=len-_next[len]; printf("%d\n",len2);
} return ;
}
Problem G.Power Strings
d.求最大的循环次数
s.最小循环节
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 1000005//字符串长度 char str[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ int len;
int len2;//最小循环节长度 while(~scanf("%s",str)){
if(str[]=='.')break; len=strlen(str);
GetNext(str);
len2=len-_next[len]; if(len%len2==){
printf("%d\n",len/len2);
}
else{
printf("1\n");
}
} return ;
}
Problem H.Seek the Name, Seek the Fame
d.给出一个字符串str，求出str中存在多少子串，使得这些子串既是str的前缀，又是str的后缀。从小到大依次输出这些子串的长度。
s.所以对于这道题，求出len处的next值，并递归的向下求出所有的next值，得到的就是答案。
c.
/*
kmp模板
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 400005//字符串长度 int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ char str[MAXN]; int sum[MAXN];
int k,len; while(~scanf("%s",str)){
GetNext(str); k=;
len=strlen(str);
for(int i=len;_next[i]>;i=_next[i]){
sum[k++]=_next[i];
} for(int i=k-;i>=;--i){
printf("%d ",sum[i]);
}
printf("%d\n",len);
} return ;
}
Problem I.Blue Jeans
d.求 N 个字符串的最长连续公共子串，N 范围是 10 ，每个串最长 60，所以可以暴力……
本来是没什么意思的，不过可以学习下string的几个函数
s.暴力。好像还能用后缀数组做，以后再看。
c.
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std; /*
涉及到string类的两个函数find和substr：
1、find函数
原型：size_t find ( const string& str, size_t pos = 0 ) const;
功能：查找子字符串第一次出现的位置。
参数说明：str为子字符串，pos为初始查找位置。
返回值：找到的话返回第一次出现的位置，否则返回string::npos 2、substr函数
原型：string substr ( size_t pos = 0, size_t n = npos ) const;
功能：获得子字符串。
参数说明：pos为起始位置（默认为0），n为结束位置（默认为npos）
返回值：子字符串
*/ int main(){ int n;
int m;
string s[]; scanf("%d",&n); while(n--){
scanf("%d",&m);
for(int i=;i<m;++i){
cin>>s[i];
} string ans="";
for(int i=;i>=;--i){//长度>=3
for(int j=;j<=-i;++j){
string tmp=s[].substr(j,i);//从j开始取i长度的子串 bool flag=true;
for(int k=;k<m;++k){
if(s[k].find(tmp)==string::npos){
flag=false;
break;
}
}
if(flag){
if(ans==""){
ans=tmp;
}
else if(tmp<ans){
ans=tmp;
}
}
}
if(ans!="")break;
} if(ans==""){
printf("no significant commonalities\n");
}
else{
cout<<ans<<endl;
}
} return ;
}
Problem J.Simpsons’ Hidden Talents
d.两个字符串s1、s2，求s1和s2的最长的相同的s1前缀和s2后缀
s.先求s1的next数组，再求s2的next数组（即代码中_next2数组，此时不是自己与自己匹配，而是与s1匹配），最后看_next2[len2]即可（len2为串s2的长度）。
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 50005//字符串长度 char s1[MAXN];
char s2[MAXN]; int _next[MAXN];//s1的next数组，s1与自己匹配
int _next2[MAXN];//s2的next数组，s2与s1匹配 void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} void GetNext2(char s[],char t[]){//s的前部与t匹配，求t相对于s的next数组（_next2[]）
int j,k,len;
//注意这几个初始化与上面不同
j=;//从0开始，首先求_next[1]
k=;//比较指针
_next2[]=;//初始值0
len=strlen(t);
while(j<len){
if(k==-||t[j]==s[k]){//指针到头了，或者相等
++j;
++k;
_next2[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ while(~scanf("%s%s",s1,s2)){ GetNext(s1);
GetNext2(s1,s2); int len2=strlen(s2);
if(_next2[len2]==){
printf("0\n");
}
else{
for(int i=;i<_next2[len2];++i){
printf("%c",s1[i]);
}
printf(" %d\n",_next2[len2]);
}
} return ;
}
Problem K.Count the string
d.统计所有前缀在串中出现的次数和
s.next数组，递推
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 200005//字符串长度
#define MOD 10007 char s[MAXN];
int dp[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ int T;
int n;
int len; int ans; scanf("%d",&T); while(T--){
scanf("%d",&n);
scanf("%s",s); GetNext(s);
len=strlen(s); ans=;
dp[]=; for(int i=;i<=len;++i){
dp[i]=dp[_next[i]]+;
dp[i]%=MOD;
ans+=dp[i];
ans%=MOD;
} printf("%d\n",ans);
} return ;
}
Problem L.Clairewd’s message（此题再看看，未完成）
d.
给出26个英文字母的加密表，明文中的'a'会转为加密表中的第一个字母，'b'转为第二个，...依次类推。
然后第二行是一个字符串（str1），形式是密文+明文，其中密文一定完整，而明文可能不完整（也可能没有）。
求出最短的完整的字符串（密文+明文）。
s.
1.用kmp来做：
首先肯定的是，给定的串中明文长度一定小于等于密文。也就是说明文长度小于等于总长的一半。
于是，取总长的后一半作为主串，然后把串反翻译一遍得到str2，然后用str2与str1的后一半进行匹配。首次把str1的后一半匹配完的位置即是给定的串中明文开始的位置。
因为是首次，所以保证了前面的密文长度最小，即总长度最小。
然后输出密文+明文，即可。
2.用扩展kmp来做：
//next[i]:x[i...m-1]与x[0...m-1]的最长公公前缀
//extend[i]:y[i...n-1]与x[0...m-1]的最长公共前缀
可以用extend数组，根据它的意义，str1作为y，str2作为x，当 i+extend[i]==len1时代表y中的从i到结尾均与x的开头匹配，如果此时i大于串长度的一半，则满足条件。
此时的i即为实际密文（明文）的长度，然后按要求输出答案即可。
c.kmp来做
/*
kmp模板
*/
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 100005//字符串长度 int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int KMPIndex(char s[],char t[]){//s的后缀等于t的前缀的最大长度
int i,j,lens,lent;
i=j=;
lens=strlen(s);
lent=strlen(t); while(i<lens&&j<lent){
if(j==-||s[i]==t[j]){
++i;
++j;
}
else j=_next[j];
}
//if(j>=lent)return i-lent;
//else return -1;
return j;
} int main(){ char str[],str1[MAXN],str2[MAXN];
char cstr[];//密文->明文
int T; scanf("%d",&T); while(T--){
scanf("%s",str);
scanf("%s",str1); for(int i=;i<;++i){//密文->明文
cstr[str[i]-'a']='a'+i;
} int len1=strlen(str1); for(int i=;i<len1;++i){
str2[i]=cstr[str1[i]-'a'];
}
str2[len1]='\0'; GetNext(str2); int len11=len1/;//假设串中明文长度（即串中明文最大长度） int num=KMPIndex(str1+len1-len11,str2);//串中实际明文长度 printf("%s",str1);
len11=len1-num;//实际密文（明文）长度
for(int i=num;i<len11;++i){
printf("%c",str2[i]);
}
printf("\n");
} return ;
}
c2.扩展kmp（略）
Problem M.Substrings
d.找出所有串的最长的公共连续子串（逆序相同也可以）
s.直接从最小的那串，枚举所有子串去寻找。反正最多100串，最长100字符。
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; int main(){ int t;
int n;
char str[][];
char subs1[],subs2[];//子串 int mi,lmi;
int tmp;
int len;
bool flag;
int ans; int len2; scanf("%d",&t); while(t--){
scanf("%d",&n); mi=;//最小长度
lmi=;//最小长度的下标 for(int i=;i<n;++i){
scanf("%s",str[i]);
tmp=strlen(str[i]);
if(tmp<mi){
mi=tmp;
lmi=i;
}
} len=strlen(str[lmi]);//最小的长度
ans=; for(int i=;i<len;++i){//子串头
for(int j=i;j<len;++j){//子串尾 for(int k=i;k<=j;++k){
subs1[k-i]=str[lmi][k];//正序
subs2[j-k]=str[lmi][k];//逆序
}
subs1[j-i+]='\0';
subs2[j-i+]='\0'; len2=strlen(subs1);
flag=true;
for(int k=;k<n;++k){
if(!strstr(str[k],subs1)&&!strstr(str[k],subs2)){
flag=false;
break;
}
} if(flag&&len2>ans){
ans=len2;
}
}
} printf("%d\n",ans); } return ;
}
Problem Z.Theme Section
d.在一个串中找 EAEBE 的形式的最长的E，其中E为一个字符串，也就是说找到前缀与后缀相同，并且串中还存在相同的一段，它们不能重复。
s.利用next数组，next[len]代表的即是最大的相同的前缀与后缀，然后让 i 从len-1往前遍历找到 i>=2（前面部分最少要有2个字符），在过程中更新最长的长度ans即可。
c.
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std; #define MAXN 1000005//字符串长度 char str[MAXN]; int _next[MAXN]; void GetNext(char t[]){//求next数组
int j,k,len;
j=;//从0开始，首先求_next[1]
k=-;//比较指针
_next[]=-;//初始值-1
len=strlen(t);
while(j<len){
if(k==-||t[j]==t[k]){//指针到头了，或者相等
++j;
++k;
_next[j]=k;//此句可由优化替代
/*优化（求匹配位置时可用）
if(t[j]!=t[k])_next[j]=k;
else _next[j]=_next[k];
//*/
}
else k=_next[k];
}
} int main(){ int N;
int len;
int m,k,ans;//m代表最大的首尾相同长度，k为i之前与开头重复的长度 scanf("%d",&N); while(N--){
scanf("%s",str);
GetNext(str); len=strlen(str);
m=_next[len];//m代表最大的首尾相同长度
ans=;
for(int i=len-;i>=;--i){
k=_next[i];//k为i之前与开头重复的长度
while(k>){
if(k<=m&&k+k<=i&&i+k<=len){//长度小于m，且三段不重合
if(k>ans)ans=k;
break;//当前是最大的长度
}
k=_next[k];//next[k]一定小于k
}
}
printf("%d\n",ans);
} return ;
}
扩展KMP：
Manacher：
最新文章
- C++四种类型转换方式。
- tomact的work目录
- CRLF和LF
- Datatable 筛选条件、排序 和获取datagrid当前页面 数据
- JS中Array详细用法
- Oracle 存储过程实例
- Use powerful plugins in your vim.
- Flume 入门--几种不同的Sources
- aui
- handlebar.js使用
- mysql 常用命令用法总结积木学院整理版
- linux中syscall调用号查看
- Android学习：代码控制UI界面示例
- mybatis不报错，但是查询结果为0
- -moz 火狐 -msIE -webkit[chrome safari]
- 使用awk分割字符串并且获取分割后的最后一个字符串
- 一段自用javascript代码
- 专访探探DBA张文升：PG在互联网应用中同样也跑的很欢畅
- 深度解析Objective-C笔试题
- Numpy常用操作方法
热门文章
- Codeforces Round #291 (Div. 2) D. R2D2 and Droid Army [线段树+线性扫一遍]
- Python入门--4--分之和循环
- H5 折线图插件
- 让Mac OS X下的终端像Linux那样拥有丰富多彩的颜色显示
- Can't connect to X11 window server using 'localhost:0.0' 的解决
- Netty构建游戏服务器(二)--Hello World
- Jetson TK1 三：项目相关安装
- BZOJ1017魔兽地图DotR 樹形DP
- Nginx配置文件语法教程
- OSX: diskutil命令-转换成自由空间并再对其分区