CF 631 D - Messenger
問題
問題概要
メッセージの履歴から自分が指定した文字列を検索したい。メッセージは特殊な形に圧縮されて送信される。そのフォーマットはというペアの列によって表される。ここで、は数字、は英小文字であり、そのペアによってという文字が個連続しているということを表している。例えば、ならばというメッセージに復元される。
そしてこの圧縮された形のメッセージがそれぞれ与えられる。の中にがいくつ含まれているか答えよ。
- は英小文字
アイデア
まず、これを複合して探索とかは考えてはいけない。文字列の長さが膨大になる可能性がある。圧縮された形の状態で探索を考える。
問題文の最後にも書いてある通り、という文字列がややなどというように様々な形で与えられうるので、これらを入力を受け付ける時に統合しておく必要がある。統合させる必要があるのは、入力を受け取った時にその1つ手前と英小文字が一致する場合であるから、実装は簡単である。
そして、愚直に1文字ずつ先頭をずらしながら調べているのでは間に合わないので、KMP法という文字列探索アルゴリズムを採用して解く。ただし、の要素数が3以上の時に、先頭と末尾を除いた部分に対して適用させる。
の要素数が1の時には単純に線形に探索して、文字が一致かつ文字数がの方が多くなるならその分(s[i]の文字数)-(t[0]の文字数)+1
のように数え上げれば良い。
の要素数が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; }