很有趣的一道题
这道题提议很难懂，其实就是让你求合法的集合数目。合法的集合定义为：
1、集合中的所有串都是s的子串，且互不重叠 2、集合中的所有串都含有子串t。
看到网上很多题解说要用kmp，但我就不用...
因为仅需进行一个字符串匹配，而hash是很好写的匹配啊
而且kmp的next指针在dp中并没有起到作用。
说一下主体思路吧：
设两个字符串为s，t，长度分别为l1,l2
首先我们在原串中查找所有的位置i，使s中以i为结尾的子串与t匹配
对于所有的位置i，标记flag[i]=1;
然后我们进行dp
设dp[i]表示以选取的所有集合中集合的最后一个元素的结尾均为i，开头为j（j不体现在状态中，1<=j<=i-l2+1）的所有方案数
那么答案就是∑（i=1~l1）dp[i]
接下来我们考虑转移
首先，对于某一位置，如果flag[i]=0，我们有：
dp[i]=dp[i-1]
原因：如果到这一位置没有匹配上，那么说明这个位置只能被包含在前一个状态中。
那么，如果flag[i]=1，怎么办？
我们考虑集合中元素的个数：
如果只有一个元素，那么由于flag[i]=1，说明i-l2+1~i与t是可以完全匹配的，所以从1到i-l2+1都可以作为这个元素的起点，所以方案数为i-l2+1
如果有两个以上元素，那么最后一个元素的起点就可以是2~i-l2+1
那么我们设这个起点是k
于是上一个元素的终点就可以是1~k-1
所以如果起点是k，总方案数就是∑(i=1~k-1)dp[i]
那这个东西就可以用一个前缀和s来维护
而由于终点可以是2~i-l2+1，所以一共的总方案数就是：
∑（i=2-i-l2+1）s[i-1]
也就是：
∑(i=1-i-l2)s[i]
发现这也是一个前缀和的形式，于是我们把s维护成一个前缀和ss
结合以上两个分析，得到转移为：
dp[i]=i-l2+1+ss[i-l2]
边递推边维护即可。
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#define seed 13131
#define ull unsigned long long
#define mode 1000000007
#define ll long long
using namespace std;
ll dp[100005];
ll s1[100005];
ll s2[100005];
char s[100005];
char t[100005];
ull has,has1[100005];
ull v;
bool flag[100005];
int main()
{
scanf("%s%s",s+1,t+1);
v=1;
int l1=strlen(s+1),l2=strlen(t+1);
for(int i=1;i<=l1;i++)
{
has1[i]=has1[i-1]*seed+s[i]-'a'+1;
}
v=1;
for(int i=1;i<=l2;i++)
{
has=has*seed+t[i]-'a'+1;
v*=seed;
}
for(int i=l2;i<=l1;i++)
{
int st=i-l2;
ull hast=has1[i]-has1[st]*v;
if(hast==has)
{
flag[i]=1;
}
}
for(int i=1;i<=l1;i++)
{
if(!flag[i])
{
dp[i]=dp[i-1];
}else
{
dp[i]=((i-l2+1)+s2[i-l2])%mode;
}
s1[i]=(s1[i-1]+dp[i])%mode;
s2[i]=(s2[i-1]+s1[i])%mode;
}
printf("%lld
",s1[l1]);
return 0;
}