BOJ 14755 Pseudoknot¶
https://www.acmicpc.net/problem/14755
편의를 위해 이 글에서는 uvz^Ru^Ryz가 아니라 xay'x'by라고 하겠습니다. 여기서 x'는 x를 거꾸로 한 문자열입니다.
풀이¶
각각의 i에 대해 다음 문제를 해결하면 됩니다.
w = xay'x'by이고, y'의 마지막 글자의 위치가 i일 때, min(|x|, |y|)의 최댓값을 구하시오.
이 값은 이분 탐색으로 찾을 수 있습니다. min(|x|, |y|) >= t를 성립시키려면, x'의 시작 위치가 i+1이면서 길이가 t 이상인 최소 길이를 찾고, y'의 마지막 위치가 i이면서 길이가 t 이상인 최소 길이를 찾고, x와 y' 및 x'과 y가 겹치지 않는지 판별하면 됩니다.
각 i마다, x'의 시작 위치가 i일 때 x'의 최대 길이를 찾습니다. [[KMP]] 실패함수처럼 보이지만, 아쉽게도 KMP는 마지막 위치가 i일 때 x의 최대 길이를 찾습니다. 그래서 w#w'라는 문자열을 새로 만들고 거기에 KMP 실패함수를 적용해 주면 됩니다. (#는 알파벳 대문자가 아닌 임의의 문자입니다.) 아래 그림에서 x = ICPC, x' = CPCI이고, 이 x'를 뒤집으면 맨 오른쪽의 ICPC에 대응됩니다.
마찬가지로, w'#w라는 문자열을 새로 만들고 KMP 실패함수를 적용해 주면, y'의 마지막 위치가 i일 때 y'의 최대 길이를 얻을 수 있습니다.
최대 길이를 구한 건 좋은데, 우리는 사실 "길이가 t 이상인 최소 길이"를 구해야 합니다. 최대 길이가 N이라고 해서 N-1, N-2, ...이 다 되지는 않습니다.
여기서 중요한 사실을 사용합니다. 가끔씩 유용하게 써먹을 수 있으니 알아둡시다.
보조정리. 1-indexed인 문자열 w의 실패함수를 F라고 할 때, (여기서 F(i)는 부분문자열의 길이와 같음)
- "i에서 끝나는 부분문자열 중 w의 접두사와 같은 것"의 최대 길이는 i이다.
- 그 조건을 만족하는 그 다음 길이는 존재할 경우 F(i)와 같으며, 존재하지 않으면 F(i) = 0이다.
- 그 조건을 만족하는 그 다음 길이는 존재할 경우 F(F(i))와 같으며, 존재하지 않으면 F(F(i)) = 0이다.
- 그 조건을 만족하는 그 다음 길이는 존재할 경우 F(F(F(i)))와 같으며, 존재하지 않으면 F(F(F(i))) = 0이다.
- ...
따라서 우리가 해야 하는 것은 F(i), F(F(i)), F(F(F(i))), ... 중 t 이상인 최소의 수를 찾는 것입니다. 이것은 LCA를 구현할 때 보았던 sparse array로 해결할 수 있습니다. i에 F를 x번 적용한 값을 F^x(i)라고 할 때, 모든 i에 대해 F^1(i), F^2(i), F^4(i), F^8(i), ..., F^131072(i)를 구합니다. 이렇게 전처리를 해 놓고, x = 131072에서 시작해서 계속 2로 나눠 가면서, F^x(i) >= t이면 i에 F^x(i)를 대입하고, 아니면 건너뛰면 됩니다.
전처리는 O(NlogN) 시간이 들고, 하나의 결정 문제는 O(logN)에 해결할 수 있고, 이것을 O(NlogN)번 반복해야 하므로 시간 복잡도는 O(Nlog^2N)입니다.
다른 풀이¶
koosaga님은 결정 문제를 풀기 위해 접미사 배열을 사용하셨습니다. koosaga님의 풀이를 링크합니다.