Submission #3107233


Source Code Expand

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

// never fail to call build() !!
// constructor()
// add(string)
// match(string, f) : [left, right], f(int left, int right, int key)
//                  : in right-asc -> left-desc order
/// --- AhoCorasick Library {{{ ///

struct AhoCorasick {
  static const int K = 26; // kinds
  struct Trie {
    // unordered_map< char, Trie* > child;
    vector<Trie*> child;
    Trie* failure = nullptr;
    Trie* next = nullptr; // next failure that has the word
    int word = -1;
    Trie(): child(K, nullptr) {}
    Trie* add(char c) {
      c-='a';
      // if(child.count(c)) {
      if(child[c]) {
        return child[c];
      } else {
        return child[c] = new Trie;
      }
    }
    Trie* go(int c) {
      if(child[c]) {
        return child[c];
      } else {
        if(failure == nullptr) { // only top can come here
          return this;
        } else {
          return failure->go(c);
        }
      }
    }
  };
  Trie* top = new Trie;
  vector< string > dict;
  void add(string word) {
    Trie* now = top;
    for(size_t i = 0; i < word.size(); i++) {
      now = now->add(word[i]);
    }
    now->word = dict.size();
    dict.emplace_back(word);
  }
  void build() {
    queue< Trie* > q;
    q.emplace(top);
    while(q.size()) {
      Trie* now = q.front();
      q.pop();
      for(int c = 0; c < K; c++) if(now->child[c]) {
        Trie* ch = now->child[c];
        q.emplace(ch);
        Trie* failure = ch->failure =
            now == top ? top : now->failure->go(c);
        ch->next = failure->word >= 0 ? failure : failure->next;
      }
    }
  }
  void match(string s, const function< void(int, int, int) >& f) {
    Trie* now = top;
    vector< tuple< int, int, int > > res;
    for(size_t i = 0; i < s.size(); i++) {
      now = now->go(s[i]-'a');
      Trie* tmp = now;
      while(tmp != nullptr && tmp != top) {
        int word = tmp->word;
        if(word >= 0) {
          f(i - dict[word].size() + 1, i, word);
        }
        tmp = tmp->next;
      }
    }
  }
};

/// }}}--- ///

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int n;
  cin >> n;
  AhoCorasick ecasd;
  for(int i = 0; i < n; i++) {
    string t;
    cin >> t;
    ecasd.add(t);
  }
  ecasd.build();
  string s;
  cin >> s;
  int m = s.size();
  const int mod = 1e9 + 7;
  vector< ll > dp(m + 1);
  dp[0] = 1;
  ecasd.match(s, [&](int le, int ri, int key) {
    dp[ri + 1] = (dp[ri + 1] + dp[le]) % mod;
  });
  cout << dp[m] << endl;
  return 0;
}

Submission Info

Submission Time
Task H - Separate String
User luma
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2658 Byte
Status AC
Exec Time 472 ms
Memory 57856 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 40
Set Name Test Cases
All 00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 10_rand_00, 10_rand_01, 10_rand_02, 10_rand_03, 10_rand_04, 11_rand_00, 11_rand_01, 11_rand_02, 11_rand_03, 11_rand_04, 20_fixed_length_00, 20_fixed_length_01, 20_fixed_length_02, 21_fixed_length_00, 21_fixed_length_01, 21_fixed_length_02, 22_fixed_length_00, 22_fixed_length_01, 22_fixed_length_02, 23_fixed_length_00, 23_fixed_length_01, 23_fixed_length_02, 24_fixed_length_00, 24_fixed_length_01, 24_fixed_length_02, 30_mixed_length_00, 30_mixed_length_01, 30_mixed_length_02, 30_mixed_length_03, 30_mixed_length_04, 90_challenge_00, 90_challenge_01, 90_challenge_02, 90_challenge_03, 90_challenge_04, 90_challenge_05
Case Name Status Exec Time Memory
00_sample_00 AC 1 ms 256 KB
00_sample_01 AC 1 ms 256 KB
00_sample_02 AC 1 ms 256 KB
00_sample_03 AC 1 ms 256 KB
10_rand_00 AC 57 ms 41472 KB
10_rand_01 AC 54 ms 45312 KB
10_rand_02 AC 63 ms 42496 KB
10_rand_03 AC 62 ms 51072 KB
10_rand_04 AC 35 ms 29952 KB
11_rand_00 AC 69 ms 56524 KB
11_rand_01 AC 71 ms 55296 KB
11_rand_02 AC 69 ms 56524 KB
11_rand_03 AC 72 ms 54528 KB
11_rand_04 AC 72 ms 53760 KB
20_fixed_length_00 AC 69 ms 45220 KB
20_fixed_length_01 AC 69 ms 45216 KB
20_fixed_length_02 AC 69 ms 45216 KB
21_fixed_length_00 AC 54 ms 57856 KB
21_fixed_length_01 AC 54 ms 57856 KB
21_fixed_length_02 AC 54 ms 57856 KB
22_fixed_length_00 AC 70 ms 55376 KB
22_fixed_length_01 AC 70 ms 55376 KB
22_fixed_length_02 AC 70 ms 55376 KB
23_fixed_length_00 AC 66 ms 57472 KB
23_fixed_length_01 AC 66 ms 57472 KB
23_fixed_length_02 AC 66 ms 57472 KB
24_fixed_length_00 AC 59 ms 56832 KB
24_fixed_length_01 AC 60 ms 56832 KB
24_fixed_length_02 AC 60 ms 56832 KB
30_mixed_length_00 AC 61 ms 57048 KB
30_mixed_length_01 AC 61 ms 57048 KB
30_mixed_length_02 AC 61 ms 57048 KB
30_mixed_length_03 AC 63 ms 57052 KB
30_mixed_length_04 AC 62 ms 57052 KB
90_challenge_00 AC 18 ms 4352 KB
90_challenge_01 AC 472 ms 1664 KB
90_challenge_02 AC 13 ms 4352 KB
90_challenge_03 AC 266 ms 1664 KB
90_challenge_04 AC 20 ms 7420 KB
90_challenge_05 AC 1 ms 256 KB