http://codeforces.com/problemset/problem/163/A?mobile=true
题目大意：给出两个串，问a的连续子串和b的子串（可以不连续）相同的个数。
思路:在LCS上加点改动
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #include<algorithm> 5 #include<iostream> 6 const int Mod=1000000007; 7 char a[500005],b[500005]; 8 int n,m,f[5005][5005]; 9 int read(){ 10 int t=0,f=1;char ch=getchar(); 11 while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();} 12 while ('0'<=ch&&ch<='9'){t=t*10+ch-'0';ch=getchar();} 13 return t*f; 14 } 15 int main(){ 16 scanf("%s",a+1);n=strlen(a+1); 17 scanf("%s",b+1);m=strlen(b+1); 18 for (int i=1;i<=n;i++) 19 if (a[i]==b[1]) f[i][1]=1; 20 for (int i=1;i<=m;i++) 21 if (a[1]==b[i]) f[1][i]=1; 22 int ans=0; 23 for (int i=1;i<=n;i++){ 24 for (int j=1;j<=m;j++){ 25 f[i][j]=f[i][j-1]; 26 if (a[i]==b[j]) 27 (f[i][j]+=f[i-1][j-1]+1)%=Mod; 28 } 29 ans=(ans+f[i][m])%Mod; 30 } 31 printf("%d ",ans); 32 }