裏紙

ほぼ競プロ、たまに日記

CF 631 D - Messenger

問題

Problem - D - Codeforces

問題概要

メッセージの履歴から自分が指定した文字列を検索したい。メッセージは特殊な形に圧縮されて送信される。そのフォーマットは(l_i , c_i)というペアの列 \{ (l_1 , c_1), (l_2 , c_2), ... (l_n , c_n) \}によって表される。ここで、lは数字、cは英小文字であり、そのペアによってcという文字がl個連続しているということを表している。例えば、 \{ (4,a), (2,b), (1,c) \}ならば aaaabbcというメッセージに復元される。

そしてこの圧縮された形のメッセージt,sがそれぞれ与えられる。tの中にsがいくつ含まれているか答えよ。

  •  1 \le |t|,|s| \le 200000
  •  1 \le l_i \le 1000000
  •  c_iは英小文字

イデア

まず、これを複合して探索とかは考えてはいけない。文字列の長さが膨大になる可能性がある。圧縮された形の状態で探索を考える。

問題文の最後にも書いてある通り、aaaaという文字列が \{ (4,a) \} \{ (1,a), (3,a) \} \{ (1,a), (2,a), (1,a) \}などというように様々な形で与えられうるので、これらを入力を受け付ける時に統合しておく必要がある。統合させる必要があるのは、入力を受け取った時にその1つ手前と英小文字が一致する場合であるから、実装は簡単である。

そして、愚直に1文字ずつ先頭をずらしながら調べているのでは間に合わないので、KMP法という文字列探索アルゴリズムを採用して解く。ただし、tの要素数が3以上の時に、先頭と末尾を除いた部分に対して適用させる。

tの要素数が1の時には単純に線形に探索して、文字が一致かつ文字数がsの方が多くなるならその分(s[i]の文字数)-(t[0]の文字数)+1のように数え上げれば良い。

tの要素数が2の時には線形に探索するのは同じだが、判定としては(s[0]の文字数>t[0]の文字数) && (s[1]の文字数>t[1]の文字数)の時に1通り数え上げることが出来る。

実装(C++)

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp(x,y) make_pair((x),(y))
#define pb(x) push_back(x)
#define fi first
#define se second

typedef pair<ll,char> p;

struct KMP
{
    vector<int> fail;
    vector<p> x;
    KMP(){}
    KMP(const vector<p> &y) :x(y)
    {
        int m=x.size();
        fail=vector<int>(m+1);
        int j=fail[0]=-1;
        for(int i=1; i<=m; i++)
        {
            while (j>=0 && x[j]!=x[i-1]) j=fail[j];
            fail[i] = ++j;
        }
    }
    vector<int> match(const vector<p> &t) {
        int n=t.size(), m=x.size();
        vector<int>ret;
        for(int i=0, k=0; i<n; i++)
        {
            while (k>=0 && x[k]!=t[i]) k=fail[k];
            if(++k >= m)
            {
                ret.push_back(i); // match at t[i-m+1 .. i]
                k=fail[k];
            }
        }
        return ret;
    }
};


int main(int argc, char const *argv[]) {
    int n,m;
    cin >>n >>m;

    vector<p> t,s;

    //input
    rep(i,n)
    {
        ll l;
        char c;
        scanf(" %lld-%c",&l,&c);

        if(t.size()==0) t.pb(p(l,c));
        else
        {
            if(t[t.size()-1].se==c) t[t.size()-1].fi+=l;
            else t.pb(p(l,c));
        }
    }
    rep(i,m)
    {
        ll l;
        char c;
        scanf(" %lld-%c",&l,&c);

        if(s.size()==0) s.pb(p(l,c));
        else{
            if(s[s.size()-1].se==c) s[s.size()-1].fi+=l;
            else s.pb(p(l,c));
        }
    }

    //solve
    ll ans=0;
    if(t.size()>=s.size())
    {
        if(s.size()==1)
        {
            rep(i,t.size())
            {
                if(t[i].se==s[0].se) ans+=max(0LL,t[i].fi-s[0].fi+1);
            }
        }
        else if(s.size()==2)
        {
            rep(i,t.size()-1)
            {
                if(t[i].se==s[0].se && t[i+1].se==s[1].se)
                {
                    if(t[i].fi>=s[0].fi && t[i+1].fi>=s[1].fi) ++ans;
                }
            }
        }
        else
        {
            vector<p> u;
            //先頭と末尾を除いた部分
            u.assign(s.begin()+1, s.end()-1);

            KMP kmp(u);
            for(const auto &i : kmp.match(t))
            {
                int l=i-u.size();
                int r=i+1;
                if(l>=0 && r<n && t[l].se==s[0].se && t[r].se==s[s.size()-1].se)
                {
                    if(t[l].fi>=s[0].fi && t[r].fi>=s[s.size()-1].fi) ++ans;
                }

            }
        }
    }
    std::cout << ans << std::endl;
    return 0;
}