Codeforces Round #344 (Div. 2) D. Messenger
解法
T の i ブロック目を T[i] と書きます(例えば T[i] = 4-a だったら実際には T[i] = "aaaa")。で, T の l ブロック目から r ブロック目をつなげたものを T[l..r] と書きます。
文字列 T の区間 [l..r] に文字列 S があるための条件は, 以下のとおりです(S のサイズを n とします)。
- T[l] の文字(c) と S[0] の文字が一致しかつT[l] の文字数(l) が S[0] の文字数以上
- T[r] の文字(c) と S[n-1] の文字が一致しかつT[l] の文字数(l) が S[n-1] の文字数以上
- T[l+1..r-1] = S[1..n-2]
この中で一番面倒なのは, T[l+1..r-1] = S[1..n-2] を満たす (l+1, r-1) の列挙です。これがすぐ終わるのであれば, あとは 各 (l, r) に対して, l と r が条件を満たしているかチェックするだけですね。
で, T[l+1..r-1] = S[1..n-2] を満たしている (l, r) の列挙は, KMP のアルゴリズムをちょっと改変すれば簡単に出来ます。
KMP については後で記事にするかもしれないです。
// kmp をやるための前計算 vector<int> makeTable(const vector<pair<char, ll> >& s) { int n = s.size(); vector<int> ret(n+1); ret[0] = -1; int j = -1; for (int i = 0; i < n; i++) { while (j >= 0 && s[i] != s[j]) j = ret[j]; ret[i+1] = ++j; } return ret; } // str の中に word とマッチする場所のリストを返す // ret のそれぞれの要素 el は, 「str[el] からの文字列が word と一致する」ことを示す vector<int> kmp(const vector<pair<char, ll> >& str, const vector<pair<char, ll> >& word) { vector<int> table = makeTable(word), ret; int m = 0, i = 0, n = str.size(); while (m+i < n) { if (word[i] == str[m+i]) { if (++i == (int)(word.size())) { ret.push_back(m); m = m+i-table[i]; i = table[i]; } } else { m = m+i-table[i]; if (i > 0) i = table[i]; } } return ret; } void create(int n, vector<pair<char, ll> >& S) { for (int i = 0; i < n; i++) { string s; cin >> s; ll l = stoll(s.substr(0, s.size()-2)); char c = s.back(); if (S.empty() || S.back().first != c) S.emplace_back(c, l); else S.back().second += l; } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n, m; cin >> n >> m; vector<pair<char, ll> > S, T; create(n, T); create(m, S); ll ans = 0; int tsize = T.size(); if (S.size() == 1) { char c = S[0].first; ll l = S[0].second; for (auto p : T) { if (p.first == c) { ans += max(0ll, p.second-l+1); } } } else if (S.size() == 2) { for (int i = 0; i < tsize-1; i++) { bool ok = true; for (int j = 0; j < 2; j++) { if (T[i+j].first != S[j].first || T[i+j].second < S[j].second) ok = false; } if (ok) ans++; } } else { pair<char, ll> start = S[0], end = S.back(); vector<pair<char, ll> > s; int ssize = S.size(); for (int i = 1; i < ssize-1; i++) s.push_back(S[i]); vector<int> memo = kmp(T, s); for (int el : memo) { if (el == 0 || el+1 == tsize) continue; if (T[el-1].first != start.first || T[el-1].second < start.second) continue; if (T[el+ssize-2].first != end.first || T[el+ssize-2].second < end.second) continue; ans++; } } cout << ans << endl; return 0; }