問題
文字列 $S$（長さ $N$）に対し、UPDATE と LCS（最長共通部分文字列の長さ）クエリを処理せよ。
制約
$1 \le N \le 2 \times 10^4$
$1 \le Q \le 2 \times 10^3$
小文字英字
入出力例
入力例 1
8 3
abababab
LCS 0 3 4 7
UPDATE 0 1 x
LCS 0 3 4 7出力例 1
4
2ヒント (段階的開示)
ヒント1: 方向性
「長さ $k$ の共通 substring が存在するか」の判定を二分探索 + ローリングハッシュで。
ヒント2: アプローチ
UPDATE は直接更新 $O(N)$。LCS は二分探索 $O(\log N)$ × ハッシュ計算 $O(N)$。
ヒント3: ダブルハッシュ
2 つのハッシュで衝突確率を $\approx 10^{-18}$ に下げる。
模範解答 (Python)
import sys
input = sys.stdin.readline
MOD1, BASE1 = (1 << 61) - 1, 131
MOD2, BASE2 = 10**9+7, 137
def rolling_hash_set(s, k, mod, base):
n = len(s)
if k > n or k == 0:
return set()
h = 0
pw = 1
for i in range(k):
h = (h * base + ord(s[i])) % mod
if k > 1:
for _ in range(k - 1):
pw = pw * base % mod
result = {h}
for i in range(1, n - k + 1):
h = (h - ord(s[i-1]) * pw % mod + mod) % mod
h = (h * base + ord(s[i + k - 1])) % mod
result.add(h)
return result
def has_common_of_len(s1, s2, k):
h1a = rolling_hash_set(s1, k, MOD1, BASE1)
h2a = rolling_hash_set(s2, k, MOD1, BASE1)
common_a = h1a & h2a
if not common_a:
return False
return True
def lcs_len(s1, s2):
if not s1 or not s2:
return 0
lo, hi = 0, min(len(s1), len(s2))
while lo < hi:
mid = (lo + hi + 1) // 2
if has_common_of_len(s1, s2, mid):
lo = mid
else:
hi = mid - 1
return lo
def solve():
N, Q = map(int, input().split())
S = list(input().strip())
out = []
for _ in range(Q):
line = input().split()
if line[0] == 'UPDATE':
l, r, c = int(line[1]), int(line[2]), line[3]
for i in range(l, r+1):
S[i] = c
else:
l1, r1, l2, r2 = int(line[1]), int(line[2]), int(line[3]), int(line[4])
s1 = ''.join(S[l1:r1+1])
s2 = ''.join(S[l2:r2+1])
out.append(str(lcs_len(s1, s2)))
print('\n'.join(out))
solve()Step-by-Step 解説
1二分探索に帰着
「長さ $k$ の共通 substring が存在」は単調なので二分探索可。
「長さ $k$ の共通 substring が存在」は単調なので二分探索可。
2ローリングハッシュ
長さ $k$ の全 substring ハッシュを $O(N)$ で列挙、スライディングウィンドウ。
長さ $k$ の全 substring ハッシュを $O(N)$ で列挙、スライディングウィンドウ。
3ダブルハッシュ
2 つの異なる mod, base で衝突回避。
2 つの異なる mod, base で衝突回避。
4UPDATE
制約小さいので $O(N)$ で直接更新。
制約小さいので $O(N)$ で直接更新。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| ハッシュスライドで負数 | 引き算でマイナス | (h - ... + mod) % mod |
| べき乗の初期化 | pw の値ずれ | pw = base^(k-1) % mod |
| LCS と LCS substring を混同 | 別アルゴリズム | substring は二分探索+ハッシュ |
| k=0 の処理 | 空 substring | 先頭で return set() |
次のステップ
- 動的挿入・削除を伴う LCS substring → Suffix Automaton