Codevs 4560 NOIP2015 D2T2 子串

> 4560 NOIP2015 D2T2 子串
 時間限制: 1 s
 空間限制: 128000 KB
 題目等級:黃金 Gold
題目描述 Description
有兩個僅包含小寫英文字母的字符串A和B。現在要從字符串A中取出k個互不重疊的非空子串，然后把這k個子串按照其在字符串A中出現的順序依次連接起來得到一個新的字符串，請問有多少種方案可以使得這個新串與字符串B相等？注意：子串取出的位置不同也認為是不同的方案。
輸入描述 Input Description
第一行是三個正整數n，m，k，分別表示字符串A的長度，字符串B的長度，以及問題描述中所提到的k，每兩個整數之間用一個空格隔開。 
第二行包含一個長度為n的字符串，表示字符串A。 第三行包含一個長度為m的字符串，表示字符串B。
輸出描述 Output Description
輸出共一行，包含一個整數，表示所求方案數。由于答案可能很大，所以這里要求輸出答案對1,000,000,007取模的結果。
樣例輸入 Sample Input
【Input1】
6 3 1 
aabaab 
aab
【Input2】
6 3 2 
aabaab 
aab
【Input3】
6 3 3 
aabaab 
aab
樣例輸出 Sample Output
【Output1】
2
【Output2】
7
【Output3】
7
數據范圍及提示 Data Size & Hint
對于第1組數據：1≤n≤500，1≤m≤50，k=1； 
對于第2組至第3組數據：1≤n≤500，1≤m≤50，k=2； 
對于第4組至第5組數據：1≤n≤500，1≤m≤50，k=m； 
對于第1組至第7組數據：1≤n≤500，1≤m≤50，1≤k≤m； 
對于第1組至第9組數據：1≤n≤1000，1≤m≤100，1≤k≤m； 
對于所有10組數據：1≤n≤1000，1≤m≤200，1≤k≤m。

/*
方案數DP+滾動數組優化.
f[i][j][p][]表示A串前i個字符B串前j個字符組成k個貢獻的方案數.
（最后一維對當前字符用不用討論）. 
當前考慮兩種狀態:兩個字符相等.兩個字符不等.
關于取模的問題相關：(a+b+c)%p=((a+b)%p+c)%p.
*/
#include<iostream>
#include<cstdio>
#define mod 1000000007
#define MAXN 1001
#define MAXM 201
using namespace std;
int f[2][MAXM][MAXM][2],n,m,k;
char s1[MAXN],s2[MAXM];
int read()
{int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();return x*f;
}
int main()
{n=read();m=read();k=read();for(int i=1;i<=n;i++)  cin>>s1[i];for(int i=1;i<=m;i++)  cin>>s2[i];f[0][0][0][0]=f[1][0][0][0]=1;for(int i=1;i<=n;i++)for(int j=1;j<=min(i,m);j++)for(int p=1;p<=k;p++){int now=i&1,last=(i-1)&1;if(s1[i]==s2[j]) f[now][j][p][1]=((f[last][j-1][p][1]+f[last][j-1][p-1][0])%mod+f[last][j-1][p-1][1])%mod,f[now][j][p][0]=(f[last][j][p][0]+f[last][j][p][1])%mod;else f[now][j][p][1]=0,f[now][j][p][0]=(f[last][j][p][0]+f[last][j][p][1])%mod;; }printf("%d",(f[n&1][m][k][0]%mod+f[n&1][m][k][1]%mod)%mod);return 0;
}