<Hash> BOJ 13713 문자열과 쿼리

문제

문자열 s가 주어질 때 각각의 쿼리에 대한 F(i)값을 구하는 문제로 F(i)의 정의는 문자열 s와 s의 부분 문자열 s.substring(0, i+1)의 공통 접미사의 길이를 의미한다.

• 문자열 s의 길이 N <= 1000000
• 쿼리의 개수 M <= 100000

접근

• 1. 각 쿼리에 대해 부분 문자열과 문자열을 하나하나 비교하여 공통 접미사의 길이를 구한다. 시간 복잡도가 $O(MN^2)$으로 문제에 적합하지 않은 풀이이다.

• 2. 공통 접미사를 찾는 과정에 대한 복잡도를 $O(1)$이나 $(logN)$에 가깝게 줄이기 위한 방법을 생각해본다. 문제의 제한이 2초인데 쿼리의 개수를 줄일 수는 없으므로!

• 3. 문자열 s에 대한 모든 부분 문자열의 Hash 값을 저장한다. (쿼리 전에 미리 처리해야 함)
  • 전처리를 하더라도 power값은 전처리보다도 미리 구해둘 것
  • 각 부분 문자열의 길이 차이 1 나는 부분 문자열의 Hash값을 이용해서 연속적으로 구할것 그렇지 않으면 $O(N^2)$으로 전처리에서 터져버린다.

• 4. 공통 접미사의 최대 길이까지는 모두 접미사가 같을 것이므로 공통 접미사의 최대 길이를 찾는 이분 탐색을 시행한다.

• 5. 접미사에 해당하는 부분을 3.에서 구한 Hash값을 이용해 구하는 방법을 생각해보자.

  • 5-1. $(i,\,j)의\,Hash\,값 = ((0,\,j)의\,Hash\,값 - (0,\,i-1)의\,Hash값) /r^{j-i+1})$
    이 방법도 좋지만 mod에서의 나눗셈이 까다로우므로 조금 바꿔주자.

  • 5-2. $(i,\,j)의\,Hash\,값 = (i,\,s.length()-1)의 Hash\,값-(j+1,\,s.length()-1)의 Hash\,값*r^{j-i}$

• 6. 총 복잡도 $O(N + M*logN)$으로 해결 가능하다.

코드

import java.io.*;
import java.util.*;

class baek__13713 {

    static int r1 = 127;
    static int m1 = 1000000007;

    static int r2 = 31;
    static int m2 = 1000000007;

    static int[] hash1;
    static int[] hash2;
    static long[][] power;

    static int[] hashing(String s, int r, int m, long[] power) {
        int[] arr = new int[s.length() + 1];

        for (int i = s.length() - 1; i >= 0; i--) {
            long before = 1L * arr[i + 1] * r;
            before %= m;
            before += (s.charAt(i) - 'a' + 1);
            before %= m;
            arr[i] = (int) before;
        }

        return arr;
    }

    static boolean check(int sl, int sr, int tl, int tr) {
        long a1 = hash1[sl] - hash1[sr] * power[1][sr - sl] % m1;
        a1 += m1;
        a1 %= m1;
        long b1 = hash1[tl] - hash1[tr] * power[1][tr - tl] % m1;
        b1 += m1;
        b1 %= m1;

        long a2 = hash2[sl] - hash2[sr] * power[2][sr - sl] % m2;
        a2 += m2;
        a2 %= m2;
        long b2 = hash2[tl] - hash2[tr] * power[2][tr - tl] % m2;
        b2 += m2;
        b2 %= m2;
        if (a1 == b1 && a2 == b2)
            return true;
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String s = br.readLine();
        int size = Integer.parseInt(br.readLine());

        power = new long[3][s.length() + 1];
        power[1][0] = 1;
        power[2][0] = 1;
        for (int i = 1; i < s.length(); i++) {
            power[1][i] = power[1][i - 1] * r1;
            power[1][i] %= m1;
            power[2][i] = power[2][i - 1] * r2;
            power[2][i] %= m2;
        }

        hash1 = new int[s.length() + 1];
        hash2 = new int[s.length() + 1];
        hash1 = hashing(s, r1, m1, power[1]);
        hash2 = hashing(s, r2, m2, power[2]);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int n = Integer.parseInt(br.readLine());

            int l = 0;
            int r = n + 1;

            while (l + 1 < r) {
                int mid = (l + r) / 2;
                if (check(s.length() - mid, s.length(), n - mid, n)) {
                    l = mid;
                } else {
                    r = mid;
                }
            }

            sb.append(l + "\n");
        }

        System.out.print(sb);
    }
}