最短串

B最短串
查找字符串与字符串是否包含时候采取KMP
将时间的复杂度由0（n*n）化作0（n）
kmp 代码如下
int contain(char p[],char s[])
{ if(!n) return n;
for (int i = 2, j = 0; i <=n; i ++ )
{
while (j && p[i] != p[j + 1]&&p[i]!='?'&&p[j + 1]!='?') j = ne[j];
if (p[i] == p[j + 1]||p[i]=='?'||p[j + 1]=='?') j ++ ;
ne[i] = j;
}
for (int i = 1, j = 0; i <=m; i ++ )
{
while (j && s[i] != p[j + 1]&&s[i]!='?'&&p[j + 1]!='?') j = ne[j];
if (s[i] == p[j + 1]||s[i]=='?'||p[j + 1]=='?') j ++ ;
if(j==n)
return n;}
return 0;
}//在稍作修改可以解决在模板链中出现多少次的问题
//全部代码如下
#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010,M=1000010;
char p[N],s[M];
int n,m;
int ne[N];
vector<int>c;
int contain(char p[],char s[])
{ if(!n) return n;
for (int i = 2, j = 0; i <=n; i ++ )
{
while (j && p[i] != p[j + 1]&&p[i]!='?'&&p[j + 1]!='?') j = ne[j];
if (p[i] == p[j + 1]||p[i]=='?'||p[j + 1]=='?') j ++ ;
ne[i] = j;
}
for (int i = 1, j = 0; i <=m; i ++ )
{
while (j && s[i] != p[j + 1]&&s[i]!='?'&&p[j + 1]!='?') j = ne[j];
if (s[i] == p[j + 1]||s[i]=='?'||p[j + 1]=='?') j ++ ;
if(j==n)
return n;}
return 0;
}
int main()
{scanf("%s%s",p+1,s+1);
n=strlen(p+1);
m=strlen(s+1);
int len=0;
if(n>m)
{swap(n,m);
len=contain(s,p);
swap(n,m);
}
else
len=contain(p,s);
if(len)
{printf("%d",m+n-len);return 0;}
int ans=n+m;
int flag,i,j;
for(i=min(n,m);i>=1;i--)
{
flag=0;
for(j=1;j<=i;j++)if(p[j]!=s[m-i+j]&&p[j]!='?'&&s[m-i+j]!='?')break;
if(j>i)flag=1;
for(j=1;j<=i;j++)if(p[n-i+j]!=s[j]&&p[n-i+j]!='?'&&s[j]!='?')break;
if(j>i)flag=1;
if(flag)ans=min(ans,n+m-i);
}
printf("%d\n",ans);
return 0;
}</int></algorithm></vector></iostream>