Submission #821385

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define REP(i, s, e) for(int i = (int)s; i < (int) e; i++)
#define rep(i, n) REP(i, 0 ,n)
#define all(x) (x).begin(), (x).end()

typedef long long ll;


string s;
ll dp[100010];
ll mod = 1e9 + 7;
string t[1010];
int n;


int main(){
  cin>>n>>s;
  rep(i, n) cin>>t[i];
  int l = s.size();
  for(int i = 0; i < n; i++){
        if(l < t[i].size())continue;
        if(s.substr(0, t[i].size()) == t[i]) dp[t[i].size()] = 1LL;
  }
  for(int i = 1; i < l; i++){
        if(dp[i] == 0LL) continue;
        for(int j = 0; j < n; j++){
          if(i + t[j].size() > l) continue;
          if(s.substr(i, t[j].size()) == t[j]) (dp[i+t[j].size()] += dp[i]) %= mod;
        }
  }
  cout<<dp[l]<<endl;
}

Submission Info

Judge Result