涉及到的知识点：KMP，扩展KMP，Manacher算法，最小最大表示
牢记住：next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度。
Number Sequence
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/
判断一个字符串是否在另一个字符串中出现，如果出现，则输出最小的位置，否则输出-1.。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
const int maxm=10010;
int a[maxn];//主串
int b[maxm];//模式串
int lena,lenb;
int nex[maxm];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int KMP()
{
int i,j;
kmp_pre();
i=j=0;
while(i<lena)
{
while(j!=-1&&a[i]!=b[j])
j=nex[j];
i++;j++;
if(j>=lenb)
return i-lenb+1;
}
return -1;
}
int main()
{
int t;rd(t);
while(t--)
{
rd2(lena,lenb);
for(int i=0;i<lena;i++)
rd(a[i]);
for(int i=0;i<lenb;i++)
rd(b[i]);
printf("%d\n",KMP());
}
return 0;
}Oulipo
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/B
问主串中含有多少个模式串，可重叠。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
const int maxm=10010;
char a[maxn];//主串
char b[maxm];//模式串
int lena,lenb;
int nex[maxm];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int KMP_count()
{
int i,j;
int ans=0;
kmp_pre();
i=j=0;
while(i<lena)
{
while(j!=-1&&a[i]!=b[j])
j=nex[j];
i++,j++;
if(j>=lenb)
{
ans++;
j=nex[j];
}
}
return ans;
}
int main()
{
int t;
rd(t);
while(t--)
{
scanf("%s",b);
scanf("%s",a);
lena=strlen(a);
lenb=strlen(b);
printf("%d\n",KMP_count());
}
return 0;
}剪花布条
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/C
求主串中含有多少个模式串，不可重叠。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
const int maxm=10010;
char a[maxn];//主串
char b[maxm];//模式串
int lena,lenb;
int nex[maxm];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int KMP_count()
{
int i,j;
int ans=0;
kmp_pre();
i=j=0;
while(i<lena)
{
while(j!=-1&&a[i]!=b[j])
j=nex[j];
i++,j++;
if(j>=lenb)
{
ans++;
j=0;
}
}
return ans;
}
int main()
{
while(scanf("%s",a)&&a[0]!='#')
{
scanf("%s",b);
lena=strlen(a);
lenb=strlen(b);
printf("%d\n",KMP_count());
}
return 0;
}Cyclic Nacklace
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/D
给定一个字符串，问最少在尾部加多少个字符，使得该字符串可以分为相等的几份。比如aaa,加0个，因为aaa是由三份a组成的，再比如abcde,那么得加5个，即abcdeabcde,
可以分为相等的两份。
原来字符串设cir=len-next[len] 意思是最小循环节的长度，如果它不等于本身的长度且lenb%cir等于0的话，就不用再加任何字符了，否则，再添加cir-lenb%cir个字符，把末尾的部分凑成一个循环节。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxm=100010;
char b[maxm];//模式串
int lenb;
int nex[maxm];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int main()
{
int t;
rd(t);
while(t--)
{
scanf("%s",b);
lenb=strlen(b);
kmp_pre();
int cir=lenb-nex[lenb];//最小循环节的长度 abbbab,循环节的长度为4，因为最后一个ab是循环节的前缀
//abababab的cir值为2
if(cir!=lenb&&lenb%cir==0)
printf("0\n");
else
printf("%d\n",cir-lenb%cir);
}
return 0;
}Period
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/E
给定一个长度为n的字符串，求它每个前缀的最短循环节，换句话说，对于每个i(2<=i<=n），求一个最大的整数K（如果K存在），使得S的前i个字符组成的前缀是某个字符串重复K次得到。输出存在K的i和对应的K。
最小循环节为i-next[i], 如果i%(i-next[i])==0且next[i]!=0的话，那么前i个字符组成的前缀一定存在循环节，循环节的个数为 i/(i-next[i])。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
int lenb;
char b[maxn];
int nex[maxn];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int main()
{
int c=1;
while(rd(lenb)!=EOF&&lenb)
{
scanf("%s",b);
kmp_pre();
printf("Test case #%d\n",c++);
for(int i=2;i<=lenb;i++)
{
int cha=i-nex[i];
if(nex[i]!=0&&i%cha==0)
printf("%d %d\n",i,i/cha);
}
printf("\n");
}
return 0;
}Power Strings
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/G
给出一个字符串，某个子串链接n次产生的，求最大的n。也就是求最小的循环节
如 aabaabaabaab，输出3
如 aabaaba ，输出7
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1010010;
int lenb;
char b[maxn];
int nex[maxn];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int main()
{
while(scanf("%s",b)==1&&b[0]!='.')
{
lenb=strlen(b);
kmp_pre();
int k=lenb-nex[lenb];//最小循环节，aabaabc，k=7
if(lenb%k==0)
printf("%d\n",lenb/k);
else
printf("1\n");
}
return 0;
}Seek the Name, Seek the Fame
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/H
给定一个字符串，有多少个前缀等于后缀，输出前缀的位置.
比如
ababcababababcabab 输出2 4 9 18
aaaaa 输出1 2 3 4 5
abaaba 输出 1 3 6
就是next[]的回溯。
以abaaba为例
位置i 0 1 2 3 4 5 6
第几个 1 2 3 4 5 6 7
字符 a b a a b a
next[i] -1 0 0 1 1 2 3
长度为6 ,注意next[6]的值，它代表的意思是前6个字母的前缀和后缀最长公共序列的长度，也就是aba
长度为6的前缀肯定是符合题意的，前缀等于后缀了.
回溯next[6]=3,也就是第6个字母往前3个字母组成的后缀(aba)和前三个字母组成的前缀
aba是相等的。再回溯next[3]=1，也就是第三个字母往前1个字母（包括第三个字母,也就是
a),和前面1个字母组成的前缀是相等的。因为 aba aba相等，那么前面aba的后缀a也就是后面aba
的后缀。
next[1]=0,结束。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=400010;
int lenb;
char b[maxn];
int nex[maxn];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int ans[maxn];
int main()
{
while(gets(b))
{
lenb=strlen(b);
kmp_pre();
int c=0;
for(int i=lenb;i!=0;i=nex[i])
{
ans[c++]=i;
}
for(int i=c-1;i>=1;i--)
cout<<ans[i]<<" ";
cout<<ans[0]<<endl;
}
return 0;
}Simpsons’ Hidden Talents
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/J
给定两个字符串s1,s2，求最长的字符串，使得该字符串是s1的前缀，是s2的后缀，输出该字符串，以及长度。
将两个字符串连接s1+s2，求next[]数组，然后从next[ (s1+s2).length() ]开始向前回溯，next[i]表示前i个字符所组成的字符串的最大前后缀匹配长度，注意回溯过程中长度p要小于等于s1的长度且小于等于s2的长度，要求最长，满足该条件，退出即可。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
string s1,s2;
int lenb;
const int maxn=50010*2;
int nex[maxn];
void kmp_pre(string b)
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int main()
{
while(cin>>s1>>s2)
{
string s=s1+s2;
int len1=s1.length();
int len2=s2.length();
lenb=s.length();
kmp_pre(s);
int p=nex[lenb];//最长的前缀=后缀，就是等于整个串
while(p>len1||p>len2) //为什么要大于len2 aaba ab这组测试数据就能解释
p=nex[p];
if(p!=0)
{
for(int i=0;i<p;i++)
cout<<s1[i];
cout<<" "<<p<<endl;
}
else
cout<<0<<endl;
}
return 0;
}Count the string
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/K
给定一个字符串，求所有的前缀在字符串中出现的次数和.
比如 abab
前缀a 出现2次
ab 出现2次
aba出现1次 abab出现1一次
dp[i]表示前i(i从1开始）个字符组成的字符串中，有多少个前缀是以第i个字符结尾的
比如前i个字符为aba，那么dp[i]=2，因为aba前缀中有 a 和aba是以a结尾的
next[i]表示前i个字符中前缀和后缀的最大匹配长度，比如前i个字符是abab那么next[4]=
那么 dp[i]=dp[next[i]]+1，为什么呢？ 假如 ababab，dp[6]=dp[4]+1，前六个字符包括前4个字符，
dp[4]是前四个字符所有前缀中以第四个字符结尾的个数，第6个字符又等于第4个字符，所以再加上它
本身ababab，就是dp[6].
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
int lenb;
const int maxn=200010;
char b[maxn];
int nex[maxn];
const int mod=10007;
int ans;
int dp[maxn];
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
int main()
{
int t;rd(t);
while(t--)
{
rd(lenb);
scanf("%s",b);
kmp_pre();
memset(dp,0,sizeof(dp));
ans=0;
for(int i=1;i<=lenb;i++)
{
dp[i]=dp[nex[i]]+1;
if(dp[i]>=mod)
dp[i]%=mod;
ans+=dp[i];
if(ans>=mod)
ans%=mod;
}
printf("%d\n",ans);
}
return 0;
}Clairewd’s message（这题参考的网上的….有些地方没明白）
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/L
S主串，T模式串
定义母串S，和字串T，设S的长度为n，T的长度为m，求S的每一个后缀与T的最长公共前缀，
也就是说，设extend数组,extend[i]表示T与S[i,n-1]的最长公共前缀，要求出所有extend[i](0<=i<n)。
设辅助数组next[i]表示T[i,m-1]和T的最长公共前缀长度
如果有一个位置extend[i]=m,则表示T在S中出现，而且是在位置i出现，这就是标准的KMP问题，
所以说拓展kmp是对KMP算法的扩展，所以一般将它称为扩展KMP算法。
资料：http://blog.csdn.net/dyx404514/article/details/41831947
本题：
给定一个转换表,也就是明文对应的暗文
再给你一个串, 里面是暗文+明文,明文不一定完整,甚至没有
让你以最短的形式补全这个串,使得前半部分为暗文,后半部分为对应的明文
原来串： 暗文+明文（明文可能没有）
译码过去： 明文+暗文
要求补齐的明文最短，那么就是求原来串的所有后缀与后来串的最长公共前缀。
因为原来串中的明文越长，需要补全的明文就越短。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=100010;
int nex[maxn];
int extend[maxn];
char s[maxn];//主串
char t[maxn];//模式串
int lens,lent;
void pre_kmp()
{
nex[0]=lent;
int j=0;
while(j+1<lent&&t[j]==t[j+1])
j++;
nex[1]=j;
int k=1;
for(int i=2;i<lent;i++)
{
int p=nex[k]+k-1;
int L=nex[i-k];
if(i+L<p+1)
nex[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<lent&&t[i+j]==t[j])
j++;
nex[i]=j;
k=i;
}
}
}
void EKMP()
{
pre_kmp();
int j=0;
while(j<lens&&j<lent&&t[j]==s[j])
j++;
extend[0]=j;
int k=0;
for(int i=1;i<lens;i++)
{
int p=extend[k]+k-1;
int L=nex[i-k];
if(i+L<p+1) extend[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<lens&&j<lent&&s[i+j]==t[j])
j++;
extend[i]=j;
k=i;
}
}
}
char table[maxn];//转换表
map<char,char>mp;
int main()
{
int cas;rd(cas);
while(cas--)
{
scanf("%s",table);
scanf("%s",s);
lens=strlen(s);
for(int i=0;i<26;i++)
mp[table[i]]='a'+i;
for(int i=0;i<lens;i++)
t[i]=mp[s[i]];
lent=strlen(t);//别忘了
s[lens]=0;
EKMP();
//以上部分把extend[i]数组求完了.
//*******************
int p;
for(p=0;p<lens;p++)
{
if(p+extend[p]>=lens&&p>=extend[p])///暂时还没有想明白.....
break;
}
for(int i=0;i<p;i++)
printf("%c",s[i]);
for(int i=0;i<p;i++)
printf("%c",mp[s[i]]);
printf("\n");
}
return 0;
}Substrings
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/M
给定n个字符串，求这n个字符串的最长公共子串，这个公共子串可以是正着的，也可以是反着的。
找到长度最小的字符串，然后枚举子串，再去其它串里查找就可以了。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=110;
int n;
string str[maxn];
int minp,p;
int main()
{
int t;
rd(t);
while(t--)
{
rd(n);
minp=10000;
for(int i=1;i<=n;i++)
{
cin>>str[i];
int tp=str[i].length();
if(minp>tp)
{
minp=tp;
p=i;
}
}
//枚举第p个串的子串
bool ok;
int ans=0;
for(int i=0;i<minp;i++)//起点
{
for(int j=1;i+j<=minp;j++)//长度
{
string s1=str[p].substr(i,j);
string s2=s1;
reverse(s2.begin(),s2.end());
//去所有串里面找
ok=1;
for(int k=1;k<=n;k++)
{
if(str[k].find(s1,0)==-1&&str[k].find(s2,0)==-1)//注意这个
{
ok=0;
break;
}
}
if(ok)
{
if(ans<j)
ans=j;
}
}
}
printf("%d\n",ans);
}
return 0;
}Corporate Identity
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/N
求n个字符串的最长公共子串。如果长度相等，则输出字典序最小的那个。
找出长度最小的字符串，然后枚举该串的子串，然后进行Kmp就可以了。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=210;
char str[4010][maxn];
int nex[maxn];
void kmp_pre(char b[],int lenb)
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(j!=-1&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
bool KMP(char a[],char b[],int lena,int lenb)
{
int i,j;
kmp_pre(b,lenb);
i=j=0;
while(i<lena)
{
while(j!=-1&&a[i]!=b[j])
j=nex[j];
i++;j++;
if(j>=lenb)
return true;
}
return false;
}
int n;
int minlen,minp;
int main()
{
while(rd(n)!=EOF&&n)
{
minlen=1000;
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
int tplen=strlen(str[i]);
if(minlen>tplen)
{
minlen=tplen;
minp=i;
}
}
char ans[210];
ans[0]='\0';
int maxlen=-1;
for(int i=0;i<minlen;i++)//枚举起点
{
for(int j=i;j<minlen;j++)//枚举终点
{
if(j-i+1<maxlen)
continue;
char tp[210];
int cnt=0;
for(int k=i;k<=j;k++)
tp[cnt++]=str[minp][k];
tp[cnt]='\0';
bool ok=1;
int lenb=j-i+1;
for(int k=1;k<=n;k++)
{
int lena=strlen(str[k]);
if(!KMP(str[k],tp,lena,lenb))
{
ok=0;
break;
}
}
if(ok)
{
maxlen=strlen(ans);
if(maxlen<lenb)
strcpy(ans,tp);
if(maxlen==lenb)
{
if(strcmp(tp,ans)<0)
strcpy(ans,tp);
}
}
}
}
if(maxlen==-1)
printf("IDENTITY LOST\n");
else
{
for(int i=0;i<maxlen;i++)
printf("%c",ans[i]);
cout<<endl;
}
}
return 0;
}String Problem
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/O
给定一个字符串比如ababab，编号为1，那么由它可以生成其它五个字符串，每次把头部的字母移到尾部。（循环同构）
ababab 1
bababa 2
ababab 3
bababa 4
ababab 5
bababa 6
求字典序最小的编号以及出现的次数，如果出现多次，输出编号最小的那个，比如字典序最小的为 ababab，一共出现了三次，编号分别为1 3 5，那么要求输出1 （最小编号）以及3（出现次数）。 还有字典序最大的编号以及出现的次数。
编号好求，用最小表示法，返回的就是最小表示法第一个字母的位置，次数就是循环节数。
字符串的最小最大表示法
http://blog.csdn.net/acm_cxlove/article/details/7909087
http://blog.csdn.net/cclsoft/article/details/5467743（这个很容易懂）
http://www.tuicool.com/articles/bmERbm
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
char b[maxn];
int nex[maxn];
int lenb;
void kmp_pre()
{
int i,j;
j=nex[0]=-1;
i=0;
while(i<lenb)
{
while(-1!=j&&b[i]!=b[j])
j=nex[j];
nex[++i]=++j;
}
}
//最小最大表示法，flag为true返回最小表示，否则返回最大表示
int min_max_exp(char b[],int lenb,bool flag)
{
int i=0,j=1,k=0;
while(i<lenb&&j<lenb&&k<lenb)
{
int t=b[(j+k)%lenb]-b[(i+k)%lenb];
if(t==0)
k++;
else
{
if(flag)
{
if(t>0) j+=k+1;
else i+=k+1;
}
else
{
if(t>0) i+=k+1;
else j+=k+1;
}
if(i==j) j++;
k=0;
}
}
return min(i,j);
}
int main()
{
while(gets(b))
{
lenb=strlen(b);
kmp_pre();
int minp=min_max_exp(b,lenb,1);
int maxp=min_max_exp(b,lenb,0);
int cir=lenb-nex[lenb];
int ans=lenb%cir?1:lenb/cir;
printf("%d %d %d %d\n",minp+1,ans,maxp+1,ans);
}
return 0;
}How many
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/P
给出n条长度相等的项链，用0 1表示，一条项链如果通过旋转和另外一条一样，
那么这两条就是同一种类。
问给出的这n条项链中有多少种类。
比如
4
0110
1100
1001
0011
0110 1100 1001 都可以旋转得到 0011
旋转也就是每次把第一个字母移到末尾就行了。
对n个字符串变换成最小表示法，然后就找有多少个不同的字符串就可以了。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=10010;
int min_max_exp(char b[],int lenb,bool flag)
{
int i=0,j=1,k=0;
while(i<lenb&&j<lenb&&k<lenb)
{
int t=b[(j+k)%lenb]-b[(i+k)%lenb];
if(t==0)
k++;
else
{
if(flag)
{
if(t>0) j+=k+1;
else i+=k+1;
}
else
{
if(t>0) i+=k+1;
else j+=k+1;
}
if(i==j) j++;
k=0;
}
}
return min(i,j);
}
int n;
map<string,int>mp;
char str[maxn][110];
int main()
{
while(rd(n)!=EOF)
{
mp.clear();
for(int i=1;i<=n;i++)
{
scanf("%s",str[i]);
int lenb=strlen(str[i]);
int p=min_max_exp(str[i],lenb,1);
string tp="";
//cout<<"pppp "<<p<<endl;
for(int k=0;k<lenb;k++)
{
int id=(p+k)%lenb;
tp.push_back(str[i][id]);
}
// cout<<"oooo "<<tp<<endl;
mp[tp]++;
}
printf("%d\n",mp.size());
}
return 0;
}Best Reward
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/S
给定26个小写字母的价值，再给定一个由26个字母组成的字符串。
把该字符串切成两部分，如果该部分是回文串，那么该串的价值为每个字母的价值和，
否则该串的价值是0，问切成的这两部分的最大价值是多少。
用扩展KMP，枚举主串的位置，分别判断前i个字母组成的第一部分串是不是回文串，再判断
剩下的一部分串是不是回文串，取最大价值。
主串s,模式串t,extend[]数组是相对于主串的，意思extend[i]意思是主串从第i个位置到末尾组成的
串与模式串整个串的最长公共前缀。
模式串t，长度为lent,next[i]表示 t[i….lent-1]的串与t[0…..lent-1]的最长公共前缀。
主串s，长度为lens,extend[i]表示s[i…..lens-1]的串与t[0…..lent-1]的最长公共前缀。
该题进行两次KMP扩展。
判断主串的前i个字母是不是回文串，用主串作模式串，反转串做主串，进行KMP扩展，就可以判断了.
判断主串剩下的字母是不是回文串，用主串还是做主串，反转串做模式串，进行KMP扩展，就可以判断了。
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=500010;
int nex[maxn];
int extend1[maxn];
int extend2[maxn];
char s[maxn];//主串
char t[maxn];//模式串
int lens,lent;
void pre_kmp(char t[],int lent)//模式串
{
nex[0]=lent;
int j=0;
while(j+1<lent&&t[j]==t[j+1])
j++;
nex[1]=j;
int k=1;
for(int i=2;i<lent;i++)
{
int p=nex[k]+k-1;
int L=nex[i-k];
if(i+L<p+1)
nex[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<lent&&t[i+j]==t[j])
j++;
nex[i]=j;
k=i;
}
}
}
void EKMP(char s[],char t[],int lens,int lent,int extend[])//主串s,模式串t
{
pre_kmp(t,lent);
int j=0;
while(j<lens&&j<lent&&t[j]==s[j])
j++;
extend[0]=j;
int k=0;
for(int i=1;i<lens;i++)
{
int p=extend[k]+k-1;
int L=nex[i-k];
if(i+L<p+1) extend[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<lens&&j<lent&&s[i+j]==t[j])
j++;
extend[i]=j;
k=i;
}
}
}
int val[26];
int sum[maxn];//疏忽了，第一次开的27，应该开字符串长度，意思是前i个字符的价值和
int n;
int main()
{
rd(n);
while(n--)
{
sum[0]=0;
for(int i=0;i<26;i++)
{
rd(val[i]);
}
scanf("%s",s);
lens=lent=strlen(s);
for(int i=1;i<=lens;i++)
{
sum[i]=sum[i-1]+val[s[i-1]-'a'];
}
for(int i=0;i<lens;i++)
{
t[i]=s[lens-i-1];
}
//第一次匹配把原串s,作为模式串，得到extend1数组
//意思是原串的前i个字母是回文串
EKMP(t,s,lent,lens,extend1);
//第二次反过来
EKMP(s,t,lens,lent,extend2);
int ans=0;//要用0
for(int i=1;i<lens;i++)
{
int tp=0;
if(extend1[lens-i]==i)//原串的前i个是回文串
tp+=sum[i];
if(extend2[i]==lens-i)
tp+=sum[lens]-sum[i];//原串的后len-i个是回文串
if(ans<tp)
ans=tp;
}
printf("%d\n",ans);
}
return 0;
}
Palindrome
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/U
裸的最长回文子串，manacher算法解决
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=1000010;
char MA[maxn<<1];
int MP[maxn<<1];
void Manacher(char s[],int len)
{
int l=0;
MA[l++]='$';
MA[l++]='#';
for(int i=0;i<len;i++)
{
MA[l++]=s[i];
MA[l++]='#';
}
MA[l]=0;
int mx=0,id=0;
for(int i=0;i<l;i++)
{
MP[i]=mx>i?min(MP[2*id-i],mx-i):1;
while(MA[i+MP[i]]==MA[i-MP[i]])
MP[i]++;
if(i+MP[i]>mx)
{
mx=i+MP[i];
id=i;
}
}
}
char s[maxn];
int main()
{
int c=1;
while(scanf("%s",s)==1)
{
if(s[0]=='E')
break;
int len=strlen(s);
Manacher(s,len);
int ans=0;
for(int i=0;i<2*len+2;i++)
ans=max(ans,MP[i]-1);
printf("Case %d: %d\n",c++,ans);
}
return 0;
}吉哥系列故事――完美队形II
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/V
要求最长的回文串，条件为左边的数到中间不递减，中间的数到右边不递增。manacher算法
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=100010;
int ma[maxn<<1];
int mp[maxn<<1];
void manacher(int s[],int len)//对s数组进行manacher，该长度为len
{
int l=0;
ma[l++]=0;
ma[l++]=-1;
for(int i=0;i<len;i++)
{
ma[l++]=s[i];
ma[l++]=-1;
}
ma[l]=-1;
int mx=0,id=0;
for(int i=0;i<l;i++)
{
mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
while(ma[i+mp[i]]==ma[i-mp[i]]&&ma[i-mp[i]]<=ma[i-mp[i]+2])//注意这个条件,保证不递减
mp[i]++;
if(i+mp[i]>mx)
{
mx=i+mp[i];
id=i;
}
}
}
int n;
int s[maxn];
int main()
{
int t;rd(t);
while(t--)
{
rd(n);
for(int i=0;i<n;i++)
rd(s[i]);
manacher(s,n);
int ans=0;
for(int i=0;i<2*n+2;i++)
ans=max(ans,mp[i]-1);
printf("%d\n",ans);
}
return 0;
}Girls’ research
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/W
首先给定一个字母ch，那么这个字母就是真正的a, 如果ch=b, 那么 b=a, c=b,d=c……….z=y, a=z…. 如果 ch=c,那么 c=a,d=b,e=c,….. ,z=x,a=y,b=z,也就是一个变换规则。
然后给定一个字符串，求该字符串的最长回文子串，输出该回文子串在原字符串中的左边界和右边界，以及按照变换规则把这部分回文子串输出。
比如样例 b babd （注意格式，中间有一个空格） , 变换规则， b->a c->b,d->c…..a->z
babd的最长回文子串是bab，左边界位置为0，右边界位置为2，按照变换规则输出该回文串为aza.
如果最长回文子串的长度为1，输出No solution!
对原串用Manacher算法求最长回文子串，并记录位置。注意输入格式
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=200010;
char ma[maxn<<1];
int mp[maxn<<1];
char str[maxn<<1];
map<int,char>change;//字母的变化保存
int ans;//最长回文子串的长度
int p;//最长回文子串中间的位置
void manacher(int len)
{
ans=-1;
int l=0;
ma[l++]='$';
ma[l++]='#';
for(int i=0;i<len;i++)
{
ma[l++]=str[i];
ma[l++]='#';
}
ma[l]=0;
int mx=0,id=0;
for(int i=0;i<l;i++)
{
mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
while(ma[i+mp[i]]==ma[i-mp[i]])
mp[i]++;
if(i+mp[i]>mx)
{
mx=i+mp[i];
id=i;
}
if(ans<mp[i]-1)
{
ans=mp[i]-1;
p=i;
}
}
}
int main()
{
char c;
while(scanf("%c %s",&c,str)!=EOF)//注意输入格式，否则超时。。
{
getchar();
int cha=c-'a';
for(int i=0;i<26;i++)
change[i]=((i+26-cha)%26+'a');
//cout<<c[0]<<" "<<str<<endl;
//for(int i=0;i<26;i++)
// cout<<change[i]<<endl;
int len=strlen(str);
manacher(len);
if(ans<2)
{
printf("No solution!\n");
continue;
}
int L=p-ans+1;//ma[]数组中对应的最长回文的左边界
int l=L/2-1;//最长回文子串对应到原数组中的左边界位置
int r=l+ans-1;//最长回文对应到原数组中的右边界位置
printf("%d %d\n",l,r);
for(int k=l;k<=r;k++)
printf("%c",change[str[k]-'a']);
printf("\n");
}
return 0;
}最长回文
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/X
学习manacher算法，复杂度O(n)
资料：http://blog.csdn.net/dyx404514/article/details/42061017
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=110010;
char MA[maxn<<1];
int MP[maxn<<1];
void Manacher(char s[],int len)
{
int l=0;
MA[l++]='$';//防止越界
MA[l++]='#';
for(int i=0;i<len;i++)
{
MA[l++]=s[i];
MA[l++]='#';
}
MA[l]=0;
int mx=0,id=0;
for(int i=0;i<l;i++)
{
MP[i]=mx>i?min(MP[2*id-i],mx-i):1;//2*id-i是关于id的对称点
while(MA[i+MP[i]]==MA[i-MP[i]])
MP[i]++;
if(i+MP[i]>mx)
{
mx=i+MP[i];
id=i;
}
}
}
char s[maxn];
int main()
{
while(scanf("%s",s)==1)
{
int len=strlen(s);
Manacher(s,len);
int ans=0;
for(int i=0;i<2*len+2;i++)
ans=max(ans,MP[i]-1);
printf("%d\n",ans);
}
return 0;
}Wow! Such Doge!
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70325#problem/Y
求给定的文本中有多少个”doge”，大小写不区分，先把所有大写字母转为小写字母，然后扫描一遍就可以了。注意输入格式。
输入：
adoge
cutedo
yourge
blownDoge
lovelyDooge
Wow! Such Dooooooooooooooge!!!
D0ge
dOge DOGE
dogedoge
输出：
6
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define rd3(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef long long ll;
const int maxn=10010;
char str[100010];
int main()
{
int cnt=0;
while(gets(str))
{
int len=strlen(str);
for(int i=0;i<len;i++)
if(isalpha(str[i]))
str[i]=tolower(str[i]);
for(int i=0;i<len;i++)
{
// cout<<"i"<<i<<endl;
if(i+3<len)
{
if(str[i]=='d'&&str[i+1]=='o'&&str[i+2]=='g'&&str[i+3]=='e')
{
cnt++;
// cout<<"oo"<<cnt<<endl;
i+=3;
}
}
}
}
printf("%d\n",cnt);
return 0;
}
今天的文章扩展kmp算法_kmz文件转kml分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/58511.html
