首页 > 代码库 > 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 子串