题目大意：给出两个串，问a的连续子串和b的子串（可以不连续）相同的个数。

思路:在LCS上加点改动

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           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\n",ans);    32 }