题解：
先用hash或者KMP预处理匹配位置；
考虑dp[i]表示以i结尾的方案数，如果 [ i-m+1 , i ]不能匹配上，那么 dp[i]=dp[i-1]
否则dp[i]=(i-m+1)+sum[i-m]+sum[i-m-1]+……+sum[0] (前面部分是新开一个串，后面表示接一个串上去)
维护前缀和、前缀和的前缀和，转移O(1)
1 #include<bits/stdc++.h> 2 #define maxn 100005 3 #define ll long long 4 using namespace std; 5 int n,m; 6 char a[maxn],b[maxn]; 7 const ll bas1=37,bas2=131; 8 const ll mod1=998244353,mod2=1000000009; 9 ll h1[maxn],xp1[maxn],h2[maxn],xp2[maxn]; 10 ll H1,H2; 11 void pre() 12 { 13 xp1[0]=1;xp2[0]=1; 14 for(int i=1;i<=n;++i)xp1[i]=xp1[i-1]*bas1%mod1; 15 for(int i=1;i<=n;++i)xp2[i]=xp2[i-1]*bas2%mod2; 16 for(int i=1;i<=n;++i)h1[i]=(h1[i-1]*bas1%mod1+a[i]-'0')%mod1; 17 for(int i=1;i<=n;++i)h2[i]=(h2[i-1]*bas2%mod2+a[i]-'0')%mod2; 18 for(int i=1;i<=m;++i)H1=(H1*bas1%mod1+b[i]-'0')%mod1; 19 for(int i=1;i<=m;++i)H2=(H2*bas2%mod2+b[i]-'0')%mod2; 20 } 21 ll gethash1(int l,int r) 22 { 23 return (h1[r]-h1[l-1]*xp1[r-l+1]%mod1+mod1)%mod1; 24 } 25 ll gethash2(int l,int r) 26 { 27 return (h2[r]-h2[l-1]*xp2[r-l+1]%mod2+mod2)%mod2; 28 } 29 bool issame(int l,int r) 30 { 31 return (gethash1(l,r)==H1)&&(gethash2(l,r)==H2); 32 } 33 const ll mod = 1000000007; 34 ll dp[maxn],s1[maxn],s2[maxn]; 35 int main() 36 { 37 scanf("%s%s",a+1,b+1); 38 n=strlen(a+1),m=strlen(b+1); 39 pre(); 40 for(int l=1,r=m;r<=n;++l,++r) 41 { 42 if(!issame(l,r))dp[r]=dp[r-1]; 43 else dp[r]=(l+s2[l-1])%mod; 44 s1[r]=s1[r-1]+dp[r];s1[r]%=mod; 45 s2[r]=s2[r-1]+s1[r];s2[r]%=mod; 46 } 47 printf("%I64d ",s1[n]); 48 return 0; 49 }