kmjp's blog

競技プログラミング参加記です

HackerRank RookieRank4 : E. DNA Value

終わってみればコードは単純。
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を使おうとしてしまった。