CodeForeces 25E (kmp)
E. Test time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output Sometimes it is hard to prepare tests for programming problems. Now Bob is preparing tests to new problem about strings — input data to his problem is one string. Bob has 3 wrong solutions to this problem. The first gives the wrong answer if the input data contains the substring s1, the second enters an infinite loop if the input data contains the substring s2, and the third requires too much memory if the input data contains the substring s3. Bob wants these solutions to fail single test. What is the minimal length of test, which couldn't be passed by all three Bob's solutions? Input There are exactly 3 lines in the input data. The i-th line contains string si. All the strings are non-empty, consists of lowercase Latin letters, the length of each string doesn't exceed 105. Output Output one number — what is minimal length of the string, containing s1, s2 and s3 as substrings. Examples input ab bc cd output 4 input abacaba abaaba x output 11
这道题目是典型的kmp应用。我们知道kmp是快速判断模式字符串是否在目标字符串中存在。先回顾一下kmp算法：
kmp算法最核心的就是next数组，写这道题目之前又把kmp算法给看了一遍：next数组实际上模式字符串中当前位置前面的字符串前缀和后缀公共的最大长度。这个比较抽象和理论，其实next数组还可以理解成模式字符串的对称程度，对称程度越高，next数组越大。在求解next数组的时候，若前面一个next数,为0，那么说明前面没有对称的，新加的字符如果要对称只可能和第一个字符开始比较。如果next数不为0，说明前面一个字符是有和它对称的，那么去找和他对称的字符的下一个字符，如果相等那么next值就++，如果不相等只能等于0了。
下面是代码实现：
void getNext(string P)
{
int len=P.length();
Next[0]=0;
for(int i=1;i<len;i++)
{
int k=Next[i-1];
while(P[i]!=P[k]&&k!=0)
k=Next[k-1];
if(P[i]==P[k])
Next[i]=k+1;
else
Next[i]=0;
}<pre name="code" class="html">}
还有一个更加精简的kmp算法
void getnext(string P )
{
int j = -1, i = 0;
int len=P.length();
next[0] = -1;
while(i < len)
{
if(j == -1 ||P[i] == P[j])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}这个两个求next数组算法虽然求得的next数组不太一样，但是都可以用于kmp。下面给kmp的算法
int kmp(string T,string P)
{
int pLen=P.length();
int tLen=T.length();
int i=0,j=0;
while(i<pLen&&j<tLen)
{
if(i==-1||P[i]==T[j])
i++,j++;
else
i=next[i];
}
if(i>=pLen) return j-pLen+1; else return -1;</pre>接下来看这道题目：题目实际上是要求两字符串头尾想拼接，也即是头尾重合的最大长度。只需要在kmp的基础上稍加改动即可，下面给出AC代码</div><div class="problem-statement" style="margin:0.5em; padding:0px; line-height:1.5em; font-size:1.4rem"></div><div class="problem-statement" style="margin:0.5em; padding:0px; line-height:1.5em; font-size:1.4rem"><pre name="code" class="html">#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
#define MAX 100000
int _next[3][MAX+5];
string a[3];
int b[3][3];
int c[3];
void get_next(string P,int pos )
{
int j = -1, i = 0;
int len=P.length();
_next[pos][0] = -1;
while(i < len)
{
if(j == -1 ||P[i] == P[j])
{
i++;
j++;
_next[pos][i] = j;
}
else
j = _next[pos][j];
}
}
int kmp(string T,string P,int pos)
{
int pLen=P.length();
int tLen=T.length();
int i=0,j=0;
while(i<pLen&&j<tLen)
{
if(i==-1||P[i]==T[j])
i++,j++;
else
i=_next[pos][i];
}
//cout<<i<<endl;
return i;
}
int main()
{
cin>>a[0]>>a[1]>>a[2];
c[0]=a[0].length();c[1]=a[1].length();c[2]=a[2].length();
memset(_next,0,sizeof(_next));
get_next(a[0],0);get_next(a[1],1);get_next(a[2],2);
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
if(i!=j)
b[i][j]=kmp(a[i],a[j],j);
int ans=0;
for(int i=0;i<3;i++)
{
for(int j=0;j<3;j++)
{
if(i==j)
continue;
for(int k=0;k<3;k++)
{
if(k==i||k==j)
continue;
if(b[i][j]==c[j])
ans=max(ans,b[i][j]+b[i][k]);
else
ans=max(ans,b[i][j]+b[j][k]);
}
}
}
printf("%d\n",c[0]+c[1]+c[2]-ans);
return 0;
}