Submission #3729011

---

Source Code Expand

#include<iostream>
#include<vector>
#include<set>
#include<map>
using namespace std;
int n;
string s[1<<17];
set<unsigned long>S[700];
map<int,int>M;
vector<unsigned long>h,make;
vector<int>le;
string t;
long dp[1<<17],mod=1e9+7;
main()
{
	cin>>n;
	int sz=0;
	for(int i=0;i<n;i++)
	{
		cin>>s[i];
		int l=s[i].size();
		if(M.find(l)==M.end())
		{
			M[l]=sz++;
			le.push_back(l);
			h.push_back(0);
			unsigned long now=1;
			for(int j=0;j<l;j++)
			{
				now=now*mod;
			}
			make.push_back(now);
		}
		unsigned long tmp=0;
		for(int j=0;j<l;j++)tmp=tmp*mod+s[i][j];
		S[M[l]].insert(tmp);
	}
	cin>>t;
	dp[0]=1;
	for(int i=0;i<t.size();i++)
	{
		for(int j=0;j<sz;j++)
		{
			h[j]=h[j]*mod+t[i];
			if(i>=le[j])h[j]-=t[i-le[j]]*make[j];
			if(i>=le[j]-1&&S[j].find(h[j])!=S[j].end())dp[i+1]=(dp[i+1]+dp[i+1-le[j]])%mod;
		}
	}
	cout<<dp[t.size()]<<endl;
}

Submission Info

Judge Result