首页 > 代码库 > vijos 1982 子串
vijos 1982 子串
感谢http://blog.csdn.net/gengmingrui/article/details/49849023
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 1050#define maxm 250#define mod 1000000007using namespace std;int n,m,l,f[2][maxn][maxm],s[2][maxn][maxm],ret;char a[maxn],b[maxm];int main(){ scanf("%d%d%d",&n,&m,&l); scanf("%s",a+1);scanf("%s",b+1); f[0][0][0]=s[0][0][0]=1; for (int i=1;i<=n;i++) s[0][i][0]=1; for (int k=1;k<=l;k++) { memset(f[k&1],0,sizeof(f[k&1])); memset(s[k&1],0,sizeof(s[k&1])); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { if (a[i]==b[j]) { f[k&1][i][j]=s[(k&1)^1][i-1][j-1]; if (a[i-1]==b[j-1]) f[k&1][i][j]=(f[k&1][i][j]+f[k&1][i-1][j-1])%mod; } s[k&1][i][j]=((s[k&1][i][j]+f[k&1][i][j])%mod+s[k&1][i-1][j])%mod; } } int ans=0; for (int i=1;i<=n;i++) ans=(ans+f[l&1][i][m])%mod; printf("%d\n",ans); return 0;}
vijos 1982 子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。