mayoko’s diary

プロコンとかいろいろ。

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;
}