bzoj5337[TJOI2018]str（Hash+dp）

用hash处理字符串匹配&＃xff0c;变成若干线段接力覆盖的问题&＃xff0c;瞎dp一下就好了qaq
复杂度O(m(len&＃43;n))O(m(len&＃43;n))

#include
#include
#include
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 10010
#define ull unsigned long long
#define k1 11113
#define mod 1000000007
inline int read(){int x&＃61;0,f&＃61;1;char ch&＃61;getchar();while(ch<&＃39;0&＃39;||ch>&＃39;9&＃39;){if(ch&＃61;&＃61;&＃39;-&＃39;)f&＃61;-1;ch&＃61;getchar();}while(ch>&＃61;&＃39;0&＃39;&&ch<&＃61;&＃39;9&＃39;) x&＃61;x*10&＃43;ch-&＃39;0&＃39;,ch&＃61;getchar();return x*f;
}
int n,m,a[2][N];
char s[N],t[N];
ull bin[N],hs[N];
inline ull calhs(int y,int x){return hs[y]-hs[x-1]*bin[y-x&＃43;1];
}
inline void inc(int &x,int y){x&＃43;&＃61;y;x%&＃61;mod;}
int main(){
// freopen("str.in","r",stdin);
// freopen("str.out","w",stdout);m&＃61;read();scanf("%s",s&＃43;1);n&＃61;strlen(s&＃43;1);bin[0]&＃61;1;int p&＃61;0;for(int i&＃61;0;i<&＃61;n;&＃43;&＃43;i) a[0][i]&＃61;1;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) bin[i]&＃61;bin[i-1]*k1,hs[i]&＃61;hs[i-1]*k1&＃43;s[i];for(int ii&＃61;1;ii<&＃61;m;&＃43;&＃43;ii){int owo&＃61;read();while(owo--){scanf("%s",t&＃43;1);int len&＃61;strlen(t&＃43;1);ull hss&＃61;0;for(int i&＃61;1;i<&＃61;len;&＃43;&＃43;i) hss&＃61;hss*k1&＃43;t[i];for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){if(i&＃43;len-1>n) break;if(calhs(i&＃43;len-1,i)!&＃61;hss) continue;inc(a[p^1][i&＃43;len-1],a[p][i-1]);}}memset(a[p],0,sizeof(a[p]));p^&＃61;1;}int ans&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) inc(ans,a[p][i]);printf("%d\n",ans);return 0;
}