ロリハの練習!!!
問題概要
長さ の文字列 T が与えられる。以下の条件を満たす最長の長さの文字列 S (反転したものを S' とする) を求めよ:
- S + S'.substr(1) + S.substr(1) + S'.substr(1) + S.substr(1) + ... の最初の 文字が と一致する
例として、T = "tabata" として、S = "tab" とすると、S からできる文字列は
- "tab"
- "tabat"
- "tabatab"
と成長して行き、最初の 6 文字が tabata になってるので適合している。
制約
解法 1: ロリハ + 調和級数
ロリハたん、基本的には長さ の文字列 に対して、ハッシュ値の累積和っぽいものを で前計算しておくことで
- 文字列 S の任意の部分文字列のハッシュ値を で計算できるようにしたもの
と思うことができる。これに対し、検索したい長さ の文字列 があったとき、S を順になめていくことでそれぞれ で照合できるので、全体として でできる。
こうして、 の中に が含まれるか、何回含まれるか、どこに含まれるか、といった情報を で計算することができる。
なんかロリハの発想は累積和そのものだよね。前計算しておけば、各区間のハッシュ値を高速に計算できる。このようなロリハのさらなるいいところとして、
- 文字列 S のロリハ
- S の反転した文字列のロリハ
を両方求めておくと、自然に反転文字列や回文なども扱いやすくなる。今回の問題も以下のように解くことができる:
- S と反転した文字列 S' のロリハを前計算しておく
- S の最初の k 文字が条件を満たすかどうかを以下のように判定する:
計算量は、各 に対して のステップが必要になるので、調和級数になって になる。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; struct RollingHash { const int base = 9973; const vector<int> mod = {999999937LL, 1000000007LL}; string S; vector<long long> hash[2], power[2]; // construct RollingHash(){} RollingHash(const string &cs) { init(cs); } void init(const string &cs) { S = cs; int n = (int)S.size(); for (int iter = 0; iter < 2; ++iter) { hash[iter].assign(n+1, 0); power[iter].assign(n+1, 1); for (int i = 0; i < n; ++i) { hash[iter][i+1] = (hash[iter][i] * base + S[i]) % mod[iter]; power[iter][i+1] = power[iter][i] * base % mod[iter]; } } } // get hash of S[left:right] inline long long get(int l, int r, int id = 0) const { long long res = hash[id][r] - hash[id][l] * power[id][r-l] % mod[id]; if (res < 0) res += mod[id]; return res; } // get lcp of S[a:] and S[b:] inline int getLCP(int a, int b) const { int len = min((int)S.size()-a, (int)S.size()-b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a+mid, 0) != get(b, b+mid, 0)) high = mid; else if (get(a, a+mid, 1) != get(b, b+mid, 1)) high = mid; else low = mid; } return low; } // get lcp of S[a:] and T[b:] inline int getLCP(const RollingHash &t, int a, int b) const { int len = min((int)S.size()-a, (int)S.size()-b); int low = -1, high = len + 1; while (high - low > 1) { int mid = (low + high) / 2; if (get(a, a+mid, 0) != t.get(b, b+mid, 0)) high = mid; else if (get(a, a+mid, 1) != t.get(b, b+mid, 1)) high = mid; else low = mid; } return low; } }; int main() { int N; string S; cin >> N >> S; N = S.size(); string rS = S; reverse(rS.begin(), rS.end()); RollingHash rh(S), rrh(rS); int ans = N; for (int len = 2; len < N; ++len) { int iter = 1; int cur = len-1; bool ok = true; while (cur < N) { int tlen = min(len, N - cur); if (iter == 0) { if (rh.get(cur, cur+tlen) != rh.get(0, tlen)) ok = false; } else { if (rh.get(cur, cur+tlen) != rrh.get(N-len, N-len+tlen)) ok = false; } iter = 1 - iter; cur += len - 1; } if (ok) { ans = len; break; } } cout << ans << endl; }
解法 2: Manacher
回文と言えば Manacher みたいなところがある。Manacher を使えば、
- 文字列 S の各 index i について、S[i] を中央とする奇数長の最長回文の半径 (中心含む)
が求められる。これを用いて、長さ len が条件を満たす条件を
- i = len-1 を中心とした半径が min(i+1, N-i)
- i = (len-1)*2 を中心とした半径が min(i+1, N-i)
- i = (len-1)*3 を中心とした半径が min(i+1, N-i)
- ...
と表すことができる。計算量はロリハと同じく になる。
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; vector<int> Manacher(const string &S) { int N = (int)S.size(); vector<int> res(N); int i = 0, j = 0; while (i < N) { while (i-j >= 0 && i+j < N && S[i-j] == S[i+j]) ++j; res[i] = j; int k = 1; while (i-k >= 0 && i+k < N && k+res[i-k] < j) res[i+k] = res[i-k], ++k; i += k, j -= k; } return res; } int main() { int N; string S; cin >> N >> S; auto rad = Manacher(S); int res = N; for (int len = 2; len < N; ++len) { bool ok = true; for (int i = len - 1; i < N; i += len - 1) { if (rad[i] != min(i+1, N-i)) ok = false; } if (ok) { res = len; break; } } cout << res << endl; }