不错的博客
求next数组:
void GetNext(char* p,int next[])
{
int pLen = strlen(p);
next[0] = -1;
int j = 0;
int k =next[j];
while (j < pLen) //最后,next[plen]也会求出来
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++k;
++j;
next[j] = k;
}
else
{
k = next[k];
}
}
}
注意:求next数组得到的最长公共前缀后缀是可以重叠的:
比如:ababa,next[5]=3,前缀为aba,后缀为aba
求next数组的方法可以优化:
void GetNextval(char* p, int next[])
{
int pLen = strlen(p);
int j = 0;
next[j] = -1;
int k = next[j];
while (j < pLen)
{
//p[k]表示前缀，p[j]表示后缀
if (k == -1 || p[j] == p[k])
{
++j;
++k;
//较之前next数组求法，改动在下面4行
if (p[j] != p[k])
next[j] = k; //之前只有这一行
else
//因为不能出现p[j] = p[ next[j ]]，所以当出现时需要继续递归，
//k = next[k] = next[next[k]]
next[j] = next[k];
}
else
{
k = next[k];
}
}
}
不同之处：
没有优化的getnext函数，next数组存的是前缀和后缀的最大匹配值，而优化后的getnext函数存的是在这个基础，进行更高效的改进。
比如abcabca
改进前最后一个字符next[7]=4,表示的是前缀和后缀最大匹配是4，即abca和abca。
改进后的next[7]=-1。这点也需要彻底搞懂，才能灵活的运用next函数。
总结一下：
在求前缀和后缀的最大匹配值时，要使用第一种，也就是未优化的算法。在运用KMP匹配字符串时，使用第二种算法，因为避免了多余的判断，更加高效。
hihoCoder #1015
题意:
求模式串在字符串中出现的次数
题解:
#include<cstdio>
#include<cstring>
using namespace std;
char pattern[10010];
int next[10010];
char str[1000010];
void getNext()
{
int len=strlen(pattern);
int j=0;
next[j]=-1;
int k=next[j];
while(j<len)
{
if(k==-1||pattern[j]==pattern[k])
{
++j;++k;
if(pattern[j]!=pattern[k]) next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
int getCnt()
{
int lens=strlen(str);
int lenp=strlen(pattern);
getNext();
int sum=0;
int i=0,j=0;
while(i<lens)
{
if(j==-1||str[i]==pattern[j])
{
j++;
i++;
}
else j=next[j];
if(j==lenp) sum++;
}
return sum;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s%s",pattern,str);
printf("%d\n",getCnt());
}
return 0;
}
Number Sequence
题意:
求模式串在字符串首次出现的位置(题目要求下标从1开始)
#include<cstdio>
#include<cstring>
using namespace std;
int p[10010],num[1000010],next[10010],n,m;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<m)
{
if(k==-1||p[j]==p[k])
{
j++;
k++;
if(p[j]!=p[k]) next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
int getIndex()
{
getNext();
int i=0,j=0,idx=-2;
while(i<n)
{
if(j==-1||num[i]==p[j])
{
i++;j++;
}
else j=next[j];
if(j==m)
{
idx=i-j;
break;
}
}
return idx;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++) scanf("%d",&num[i]);
for(int i=0;i<m;i++) scanf("%d",&p[i]);
printf("%d\n",getIndex()+1);
}
return 0;
}
剪花布条
题意:
求模式串在字符串中的不重叠的出现次数
题解:
kmp匹配时,如果发现j==plen,那么j赋为0
#include<cstdio>
#include<cstring>
using namespace std;
char str[1010],p[1010];
int next[1010],slen,plen;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
k++;
j++;
if(p[j]!=p[k]) next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
int getUnReptitionCnt()
{
getNext();
int i=0,j=0,sum=0;
while(i<slen)
{
if(j==-1||str[i]==p[j])
{
i++;
j++;
}
else j=next[j];
if(j==plen)
{
sum++;
j=0;
}
}
return sum;
}
int main()
{
while(scanf("%s",str)!=EOF)
{
slen=strlen(str);
if(str[0]=='#'&&slen==1) break;
scanf("%s",p);
plen=strlen(p);
printf("%d\n",getUnReptitionCnt());
}
return 0;
}
Cyclic Nacklace
题意:
求字符串最小循环节
(最小循环节是不可重叠的:比如ababa:最小循环节是ab,而不是aba)
题解:
注意:求最小循环节时不可以用优化的方法求next数组
#include<cstdio>
#include<cstring>
using namespace std;
char p[100010];
int plen,next[100010];
void getNext()//求最小循环节时不可以用优化的方法求next数组
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",p);
plen=strlen(p);
getNext();
int minRepetend=plen-next[plen];//最小循环节长度
if(minRepetend!=plen&&plen%minRepetend==0) printf("0\n");
else printf("%d\n",minRepetend-plen%minRepetend);
}
return 0;
}
Period
题意:
给出一个字符串,如果它的某个前缀可以表示为循环k次的串,求出前缀index和k(k>1)
题解:
如果i%(i-next[i])==0,那么这个[0,i-1]的字符串可以表示为循环字符串
#include<cstdio>
#include<cstring>
using namespace std;
char p[1000010];
int plen,next[1000010];
void getNext()//求最小循环节时不可以用优化的方法求next数组
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
}
void solve()
{
int i=2;
getNext();
while(i<=plen)
{
if(next[i]!=0&&(i%(i-next[i])==0))
{
printf("%d %d\n",i,i/(i-next[i]));
}
i++;
}
printf("\n");
}
int main()
{
int cas=1;
while(scanf("%d",&plen)!=EOF,plen)
{
scanf("%s",p);
printf("Test case #%d\n",cas++);
solve();
}
return 0;
}
亲和串
题意:
亲和串的定义是这样的：给定两个字符串s1和s2,如果能通过s1循环移位，使s2包含在s1中，那么我们就说s2 是s1的亲和串。
题解:
将s1扩大一倍,即把s1的字符复制一遍,然后判断s2是不是在s1中。当然,如果s1原来的大小小于s2,那s1通过循环移位也不能包含s2
#include<cstdio>
#include<cstring>
using namespace std;
char str[200010];
char p[100010];
int next[100000];
int plen,slen;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
j++;
k++;
if(p[j]!=p[k]) next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
bool contains()
{
int i=0,j=0;
while(i<slen)
{
if(j==-1||str[i]==p[j])
{
i++;
j++;
}
else j=next[j];
if(j==plen) return true;
}
return false;
}
int main()
{
while(scanf("%s",str)!=EOF)
{
slen=strlen(str);
scanf("%s",p);
plen=strlen(p);
if(plen>slen)
{
printf("no\n");
continue;
}
for(int i=0;i<slen;i++)
{
str[i+slen]=str[i];
}
slen<<=1;
str[slen]=0;
getNext();
if(contains()) printf("yes\n");
else printf("no\n");
}
return 0;
}
The Minimum Length
求最小循环节...不贴代码了
Power Strings
题意:
也是求最小循环节了
题解:
#include<cstdio>
#include<cstring>
using namespace std;
char p[1000010];
int next[1000010];
int plen;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[k]==p[j])
{
next[++j]=++k;
}
else k=next[k];
}
}
int main()
{
while(scanf("%s",p)!=EOF)
{
plen=strlen(p);
if(plen==1&&p[0]=='.') break;
getNext();
if(plen%(plen-next[plen])==0) printf("%d\n",plen/(plen-next[plen]));
else printf("1\n");
}
return 0;
}
Seek the Name, Seek the Fame
题意:
给定字符串,求出字符串的所有的公共前缀后缀
题解:
其实就是不断调用next数组,以寻找更短的公共前缀后缀
#include<cstdio>
#include<cstring>
using namespace std;
char p[400010];
int next[400010];
int plen;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
void out(int j)
{
if(next[j]==0) return;
out(next[j]);
printf("%d ",next[j]);
}
int main()
{
while(scanf("%s",p)!=EOF)
{
plen=strlen(p);
getNext();
out(plen);
printf("%d\n",plen);
}
return 0;
}
Blue Jeans
题意:
给出n个字符串,找出最长的公共子串,如果有多个,输出字典顺序最小的那个
题解:
暴力拆分第一个字符串的每一个子串(子串长度>=3),然后构造子串的next数组,然后用子串匹配每个2-n这些字符串(匹配时从长度大的子串开始),如果这n-1个字符串都可以成功匹配,那么得出答案
ps:可以通过二分最大长度的方法优化
#include<cstdio>
#include<cstring>
using namespace std;
const int LEN=60;
char str[15][65];
char cpy[65];
char ans[65];
int next[65];
void getNext(char *p,int *next,int len)
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<len)
{
if(k==-1||p[j]==p[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
bool contains(char *str,char *p,int plen)
{
int i=0,j=0;
while(i<LEN)
{
if(j==-1||str[i]==p[j])
{
i++;j++;
}
else j=next[j];
if(j==plen) return true;
}
return false;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
}
bool found=false;
memset(cpy,0,sizeof(cpy));
ans[0]='Z';
for(int len=60;len>=3;len--)//子串长度
{
if(found) break;
for(int st=0;st+len-1<60;st++)//子串的开始坐标
{
for(int i=0,j=st;i<len;i++,j++)
{
cpy[i]=str[1][j];
}
cpy[len]=0;
getNext(cpy,next,len);
bool allContains=true;
for(int j=2;j<=n;j++)
{
if(!contains(str[j],cpy,len))
{
allContains=false;
break;
}
}
if(allContains)
{
found=true;
if(strcmp(ans,cpy)>0)//字典顺序小的优先
{
strcpy(ans,cpy);
ans[len]=0;
}
}
}
}
if(found) printf("%s\n",ans);
else printf("no significant commonalities\n");
}
return 0;
}
Simpsons’ Hidden Talents
题意:
给定两个字符串s1,s2,求最长的s1前缀ss使得ss为s2的后缀,输出该字符串和其长度。
题解:
将s1,s2合并后再求整个字符串求next数组,next[len1+len2]就是答案了;
但是next[len]可能会大于len1或大于len2,所以要不断找更短的公共前缀后缀
#include<cstdio>
#include<cstring>
using namespace std;
char p[100010];
int next[100010];
int plen,len1,len2;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
int main()
{
while(scanf("%s",p)!=EOF)
{
len1=strlen(p);
scanf("%s",p+len1);
plen=strlen(p);
len2=plen-len1;
getNext();
if(next[plen]==0||next[plen]==-1)
{
printf("0\n");
}
else
{
while(next[plen]>len1||next[plen]>len2) plen=next[plen];
p[next[plen]]=0;
printf("%s %d\n",p,next[plen]);
}
}
return 0;
}
Count the string
题意:
求出每个前缀在串中的出现次数的总和
题解:
求出next数组,枚举区间的最长公共前后缀以及更短的的公共前后缀
#include<cstdio>
#include<cstring>
using namespace std;
const int MOD=10007;
char p[200010];
int next[200010];
int plen;
void getNext()
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
next[++j]=++k;
}
else k=next[k];
}
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%s",&plen,p);
getNext();
int sum=0;
for(int i=1;i<=plen;i++)
{
sum=(sum+1)%MOD;//加上前缀str[0,i-1]本身
int tmp=next[i];
while(tmp)//枚举区间的最长公共前后缀以及更短的的公共前后缀
{
sum=(sum+1)%MOD;
tmp=next[tmp];
}
}
printf("%d\n",sum);
}
return 0;
}
Substrings
题意:
找到一个子串x，满足x或x的逆串是输入的n个字符串的子串，求长度最大的x，输出x的长度
题解:
其实和上面Blue Jeans那道题一样的,对第一个字符串暴力拆分,求出它的所有子串,求出next数组,然后对剩下的n-1个字符串正序kmp或者逆序kmp就可以了
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=110;
char str[MAXN][MAXN];
char cpy[MAXN];
int next[MAXN];
int slen[MAXN];
void getNext(char *p,int *next,int plen)
{
int j=0;
next[j]=-1;
int k=next[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
j++;k++;
if(p[j]!=p[k]) next[j]=k;
else next[j]=next[k];
}
else k=next[k];
}
}
bool contains(char *str,char *p,int slen,int plen)
{
int i=0,j=0;
while(i<slen)
{
if(j==-1||str[i]==p[j])
{
i++;j++;
}
else j=next[j];
if(j==plen) return true;
}
return false;
}
bool reverContains(char *str,char *p,int slen,int plen)
{
int i=slen-1,j=0;
while(i>=0)
{
if(j==-1||str[i]==p[j])
{
i--;j++;
}
else j=next[j];
if(j==plen) return true;
}
return false;
}
int main()
{
int t,n;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
slen[i]=strlen(str[i]);
}
int length=strlen(str[1]);
bool found=false;
for(int len=length;len>=1;len--)
{
if(found) break;
for(int st=0;st+len-1<length;st++)
{
for(int i=0,j=st;i<len;i++,j++)
{
cpy[i]=str[1][j];
}
cpy[len]=0;
getNext(cpy,next,len);
bool all=true;
for(int i=2;i<=n;i++)
{
if(!contains(str[i],cpy,slen[i],len))
{
if(!reverContains(str[i],cpy,slen[i],len))
{
all=false;
break;
}
}
}
if(all)
{
found=true;
break;
}
};
}
if(found) printf("%d\n",strlen(cpy));
else printf("0\n");
}
return 0;
}
Corporate Identity
题意:
求所有字符的最长公共子串
#include<stdio.h>
#include<string.h>
char str[4040][220];
int next[4040];
void getnext(char *s)
{
int len=strlen(s);
int j=0,k=-1;
next[0]=-1;
while(j<=len)
{
if(k==-1||s[k]==s[j])
{
k++;
j++;
next[j]=k;
}
else
k=next[k];
}
}
int kmp(char *a,char *b)
{
int i,j;
i=j=0;
int n=strlen(a);
int m=strlen(b);
getnext(b);
while(i<n)
{
if(j==-1||a[i]==b[j])
{
i++;
j++;
}
else
j=next[j];
if(j==m)
return 1;
}
return 0;
}
int main()
{
int n;
while(scanf("%d",&n),n)
{
int i,j,k;
for(i=0;i<n;i++)
{
scanf("%s",str[i]);
}
int len=strlen(str[0]);
char temp[220],ans[220]="";
for(i=0;i<len;i++)
{
int cnt=0;
for(j=i;j<len;j++)
{
temp[cnt++]=str[0][j];
temp[cnt]='\0';
int flag=0;
for(k=1;k<n;k++)
{
if(!kmp(str[k],temp))
{
flag=1;
break;
}
}
if(!flag)
{
if(strlen(temp)>strlen(ans)||(strlen(temp)==strlen(ans)&&strcmp(temp,ans)<0))
memcpy(ans,temp,sizeof(temp));
}
}
}
if(strlen(ans)==0)
printf("IDENTITY LOST\n");
else
printf("%s\n",ans);
}
}
String Problem
题意：
给定一个字符串S，在S所有的字符同构字符串中，求出字典序最小的同构字符串的开始位置以及它的出现次数和字典序最大的字符串的开始位置以及它的出现次数．
题解：
显然，当Ｓ刚好啥由循环节构成的字符串时，出现次数是循环节的个数，否则是出现次数是1，而那两个字典序刚好可以通过最小最大表示法求出来
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int MAXN=1000010;
int nxt[MAXN],plen;
char p[MAXN];
void getNext()
{
int j=0;
nxt[j]=-1;
int k=nxt[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
nxt[++j]=++k;
}
else k=nxt[k];
}
}
int getMin()
{
int i=0,j=1,k=0;
while(i<plen&&j<plen&&k<plen)
{
int tmp=p[(i+k)%plen]-p[(j+k)%plen];
if(tmp==0) k++;
else
{
if(tmp>0) i=i+k+1;
else j=j+k+1;
if(i==j) j++;
k=0;
}
}
return min(i,j);
}
int getMax()
{
int i=0,j=1,k=0;
while(i<plen&&j<plen&&k<plen)
{
int tmp=p[(i+k)%plen]-p[(j+k)%plen];
if(tmp==0) k++;
else
{
if(tmp>0) j=j+k+1;
else i=i+k+1;
if(i==j) j++;
k=0;
}
}
return min(i,j);
}
int main()
{
while(scanf("%s",p)!=EOF)
{
plen=strlen(p);
getNext();
int len=plen-nxt[plen];
int minIndex=getMin()+1;
int maxIndex=getMax()+1;
if(plen%len==0) printf("%d %d %d %d\n",minIndex,plen/len,maxIndex,plen/len);
else printf("%d %d %d %d\n",minIndex,1,maxIndex,1);
}
}
How many
题意：
给定n个字符串，找出不同的循环同构字符串的个数。
题解：
用最小表示法表示每个字符串，然后再用set或者排序的方法去重即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
const int MAXN=110;
char str[MAXN];
char cpy[MAXN];
int len;
int getMin(char *str)
{
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len)
{
int tmp=str[(i+k)%len]-str[(j+k)%len];
if(tmp==0) k++;
else
{
if(tmp>0) i=i+k+1;
else j=j+k+1;
if(i==j) j++;
k=0;
}
}
return min(i,j);
}
int main()
{
int n,index,i,j;
set<string> ss;
while(scanf("%d",&n)!=EOF)
{
ss.clear();
while(n--)
{
scanf("%s",str);
len=strlen(str);
index=getMin(str);
for(i=index,j=0;i<len;i++,j++)
{
cpy[j]=str[i];
}
for(i=0;j<len;j++,i++)
{
cpy[j]=str[i];
}
cpy[len]=0;
ss.insert(cpy);
}
printf("%d\n",ss.size());
}
}
Problem 1901 Period II
题意：
找出所有的ｐ，满足：For each prefix with length P of a given string S,if
S[i]=S[i+P] for i in [0..SIZE(S)-p-1],
题解：
其实就是next数组的应用，不断得到更短的最长公共前缀后缀
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000010;
int nxt[MAXN],plen;
char p[MAXN];
void getNext()
{
int j=0;
nxt[j]=-1;
int k=nxt[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
nxt[++j]=++k;
}
else k=nxt[k];
}
}
int main()
{
int t,j;
scanf("%d",&t);
queue<int> que;
for(int cas=1;cas<=t;cas++)
{
scanf("%s",p);
plen=strlen(p);
getNext();
j=plen;
while(nxt[j]!=0&&nxt[j]!=-1)
{
que.push(plen-nxt[j]);
j=nxt[j];
}
printf("Case #%d: %d\n",cas,que.size()+1);
while(!que.empty())
{
printf("%d ",que.front());
que.pop();
}
printf("%d\n",plen);
}
}
Theme Section
题意：
给定一个字符串，找出能构成"EAEBE"形式的字符串的E的最长长度。
题解：
因为前面和后面都是E，所以容易想到next数组，然后不断求更短的公共前缀后缀长度，再判断中间是不是包含E就可以了，判断的方法是next[j]是不是等于当前的E的长度
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=1e6+10;
char p[MAXN];
char cpy[MAXN];
int nxt[MAXN];
int plen;
void getFail()
{
int j=0;
nxt[j]=-1;
int k=nxt[j];
while(j<plen)
{
if(k==-1||p[j]==p[k])
{
nxt[++j]=++k;
}
else k=nxt[k];
}
}
int solve()
{
for(int i=nxt[plen];i;i=nxt[i])
{
for(int j=2*i;j<=plen-i+1;j++)//不重叠
{
if(nxt[j]==i)
{
return i;
}
}
}
return 0;
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
scanf("%s",p);
plen=strlen(p);
getFail();
printf("%d\n",solve());
}
return 0;
}
