for (int j=p+1;j<n-1;j++){  for (int k=j+1;k<n;k++){       rig[i] += rig[k];  }       rig[i]++;    }rig[i]++;

 1 #include <cstdio> 2 #include <cstring> 3 #include <vector> 4 using namespace std; 5 #define N 100000 6 vector<int> gp; 7 char s[N+20],t[N+20]; 8 int p[N+20]; 9 long long rig[N+20],sum[N+20],ans[N+20];10 const int mod = (int)(1e9+7);11 void get_next(char *str)12 {13     int i = 0,j = -1, l = strlen(str);14     p[0] = -1;15     while (i<l)16     {17         if (j==-1||str[i]==str[j]) p[++i] = ++j;18         else j = p[j];19     }20 }21 bool KMP(char *s1,char *s2)  //串s1中寻找串s222 {23     int l1 = strlen(s1), l2 = strlen(s2), i = 0, j = 0;24     while (i<l1&&j<l2)25     {26         if (j==-1||s1[i]==s2[j]) i++,j++;27         else j= p[j];28         if (j==l2){29             gp.push_back(i-1);30             j = p[j];31         }32     }33 }34 int main(){35     scanf("%s%s",s,t);36     get_next(t);37     KMP(s,t);38     int n = strlen(s);39     int m = strlen(t);40     for (int i=n-1;i>=0;i--){41         vector<int>::iterator it = lower_bound(gp.begin(),gp.end(),i+m-1);42         if (it!=gp.end()){43             int j = *it;44             rig[i] = (ans[j+1] + n-j) % mod;45             sum[i] = (sum[i+1] + rig[i]) % mod;46             ans[i] = (ans[i+1] + sum[i]) % mod;47         }48     }49     long long res = 0;50     for (int i=0;i<n;i++) res = (res + rig[i]) % mod;51     printf("%I64d\n",res);52     return 0;53 }