几道用到KMP的DP题：
hdu 5763 hdu 3689 hdu 3336 codeforces 494B codevs 3945
关于KMP的nx数组：
如果在本文中看见了nx[]指的是所谓“成功指针”，或者getnx()函数跟本人之前的板子写的不一样......
都是因为求nx数组有两种方法！！！
详情请阅本人的另一篇文章：关于KMP算法的重大发现
好了我们进入正题~
一道一道来~
hdu 5763 Another Meaning
题意及样例：原题链接
设第一个串为A，长为n；第二个串为B，长为L
从1到n计算1~k能代表的意思的数量f[k]
如果A[k-L+1,k]==B
则f[k]=f[k-L]+f[k-1]
否则f[k]=f[k-1]
判断A[k-L+1,k]是否与B匹配就要靠KMP了
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std; int t,al,bl;
char a[];
char b[];
int nx[];
int fl[];
int f[]; void getnx()
{
nx[]=;
for(int i=,j=;i<=bl;)
{
nx[i]=j;
while(j&&b[j]!=b[i])j=nx[j];
j++,i++;
}
} void kmp()
{
for(int i=,j=;i<=al;)
{
while(j&&b[j]!=a[i])j=nx[j];
if(j==bl)
{
fl[i]=;
j=nx[j];
}
else j++,i++;
}
} int main()
{
scanf("%d",&t);
for(int cs=;cs<=t;cs++)
{
memset(a,,sizeof(a));
memset(b,,sizeof(b));
memset(fl,,sizeof(fl));
scanf("%s",a+);
scanf("%s",b+);
al=strlen(a+);
bl=strlen(b+);
getnx();
kmp();
f[]=;
for(int i=;i<=al;i++)
{
if(fl[i])f[i]=(f[i-]+f[i-bl])%mod;
else f[i]=f[i-];
}
printf("Case #%d: %d\n",cs,f[al]);
}
return ;
}
hdu 5763 Another Meaning
hdu 3689 Infinite monkey theorem
概率DP，不一定一出错就要重头开始打。用nx[ ]数组转移，避免字符的浪费。
这里的nx[ ]数组指的是成功指针......（玄学）
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int n,m,len;
double p[];
char s[];
char key[];
int nx[];
double f[][]; void getnx()
{
nx[]=;
for(int i=,j=;i<=len;i++)
{
while(j&&s[i]!=s[j+])j=nx[j];
if(s[j+]==s[i])j++;
nx[i]=j;
}
} int main()
{
while(true)
{
memset(nx,,sizeof(nx));
for(int i=;i<=;i++)p[i]=0.00;
for(int i=;i<=;i++)
{
for(int j=;j<=;j++)
{
f[i][j]=0.00;
}
}
scanf("%d%d",&n,&m);
if(!n)return ;
for(int i=;i<=n;i++)
{
char c[];
scanf("%s",c+);
key[i]=c[];
scanf("%lf",&p[i]);
}
scanf("%s",s+);
len=strlen(s+);
getnx();
f[][]=1.00;
for(int i=;i<=m;i++)
{
for(int j=;j<len;j++)
{
for(int k=;k<=n;k++)
{
int ps=j;
while(ps&&s[ps+]!=key[k])ps=nx[ps];
if(s[ps+]==key[k])ps++;
f[i][ps]+=f[i-][j]*p[k];
}
}
}
double ans=0.00;
for(int i=;i<=m;i++)ans+=f[i][len];
printf("%.2lf%%\n",ans*100.00);
}
}
hdu 3689 Infinite monkey theorem
hdu 3336 Count the string
利用KMP中nx[ ]数组的性质。
上代码。
#include<cstdio>
#include<cstring>
using namespace std; int t,n,len,f[],ans;
char s[];
int nx[]; void getnx()
{
for(int i=;i<n;i++)
{
int j=nx[i];
while(j&&s[i]!=s[j]) j=nx[j];
nx[i+]= s[i]==s[j] ? j+:;
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
scanf("%s",s);
len=strlen(s);
getnx();
memset(f,,sizeof(f));
ans=;
for(int i=;i<=n;i++)
{
f[i]=f[nx[i]]+;
ans+=f[i];
f[i]%=;
ans%=;
}
printf("%d\n",ans);
}
}
hdu 3336 Count the string
CodeForces 494B Obsessive String
比较复杂......
记录f[ ]，f[ ]的前缀和s[ ]，还有s[ ]的前缀和ss[ ] 。
KMP用来匹配字符串。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define mod 1000000007
using namespace std; char a[],b[];
int al,bl;
int nx[];
int fl[];
int f[],s[],ss[]; void getnx()
{
nx[]=;
for(int i=,j=;i<=bl;)
{
nx[i]=j;
while(j&&b[j]!=b[i])j=nx[j];
i++,j++;
}
} void kmp()
{
for(int i=,j=;i<=al;)
{
while(j&&a[i]!=b[j])j=nx[j];
if(j==bl)fl[i]=,j=nx[j];
else i++,j++;
}
} int main()
{
scanf("%s",a+);
al=strlen(a+);
scanf("%s",b+);
bl=strlen(b+);
getnx();
kmp();
for(int i=;i<=al;i++)
{
if(fl[i])f[i]=(i-bl++ss[i-bl])%mod;
else f[i]=f[i-];
s[i]=(s[i-]+f[i])%mod;
ss[i]=(ss[i-]+s[i])%mod;
}
int ans=;
for(int i=;i<=al;i++)ans=(ans+f[i])%mod;
printf("%d",ans);
}
CodeForces 494B Obsessive String
CODEVS 3945 完美拓印
当成字符串匹配......
坑挺多的，各种方向都得匹配一次求出答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std; int a[],b[],s1[],s2[],nx[];
int n,m,ans; void getnx()
{
nx[]=nx[]=;
for(int i=;i<n;i++)
{
int j=nx[i];
while(j&&s1[i]!=s1[j])j=nx[j];
nx[i+]=(s1[i]==s1[j]?j+:);
}
} int kmp()
{
getnx();
int j=,cnt=;
for(int i=;i<m;i++)
{
while(j&&s2[i]!=s1[j])j=nx[j];
if(s2[i]==s1[j])j++;
if(j==n)cnt++,j=nx[j];
}
return cnt;
} int main()
{
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]);
if(n==)
{
printf("%d\n",m<<);
return ;
}
n--; m--;
for(int i=;i<n;i++)s1[i]=a[i+]-a[i];
for(int i=;i<m;i++)s2[i]=b[i+]-b[i];
ans+=kmp();
for(int i=;i<n;i++)s1[i]=a[n-i]-a[n-i-];
ans+=kmp();
for(int i=;i<n;i++)s1[i]=;
ans+=*kmp();
printf("%d",ans);
return ;
}
CODEVS 3945 完美拓印
结束了。
最后顺便说，有些字符串匹配的题可以用hash做。
这样可以偷懒，不用写KMP
好吧还是乖乖背KMP板子吧。
溜了。