終わってみればコードは単純。
https://www.hackerrank.com/contests/rookierank-4/challenges/dna-value
問題
N文字の文字列Sが与えられる。
各位置iに対し、f(i)を求めよ。
f(i)はS[i]を先頭とするk文字の文字列のうち、以下を満たす最大のkで定義される。
- S[i...(i+1-k)]がSのprefix S[0...(k-1)]と等しい
- S[i]を最後尾とするSの部分列S[(i-(k-1))...i)]とも等しい
解法
まず前半の条件を考え、Z-algorithmを適用しよう。
i文字目に相当するZ-algorithmの結果をZ(i)とする。
この時点で0≦k≦Z(i)でなければならない。
次に後者を考える。
後者の条件を満たすには、S[(i-(k-1))...i)]がk以上でなければならない。
逆に言えばZ(i-(k-1))がk以上となる最大のkを求めればよい。
これは尺取り法の要領で解くことができる。
S[j]を前から順に処理していくことを考える。
i=j-(k-1)とし、S[i..j]=S[j..(j+k-1)]となる最小のiを求めたい。
S[j]を考える際、iの候補は0≦j-i≦Z[j]-1かつZ[i]≧(j-i+1)であり、条件を満たす最小のiを求めるとf(j)=j-i+1となる。
後者の不等式を言い換えると、j>i+Z[i]-1となるjではiは候補となりえない。
よって尺取り法の要領でjを更新するたびに条件を満たさないiを適宜取り除いていけばよい。
残ったiの最小値をf(j)=j-i+1に適用すればよい。
int N; string S; set<int> C; vector<int> del[505050]; vector<int> Zalgo(string s) { vector<int> v(1,s.size()); for(int i=1,l=-1,r=-1;i<s.size();i++) { if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]); else { l=i; r=(i>r)?i:(r+1); while(r<s.size() && s[r-i]==s[r]) r++; v.push_back((r--)-l); } } v.push_back(0); return v; } void solve() { int i,j,k,l,r,x,y; string s; cin>>S; N=S.size(); vector<int> Z=Zalgo(S); FOR(i,N) { FORR(e,del[i]) C.erase(e); if(Z[i]==0) { _P("%d ",0); } else { C.insert(i); del[i+Z[i]].push_back(i); x=Z[i]; auto it=C.lower_bound(i-(Z[i]-1)); _P("%d ",i-*it+1); } } _P("\n"); }
まとめ
最初SegTreeを使おうとしてしまった。