백준26640 Palindrom

작성일 | In

문제 링크

  • http://icpc.me/26640

사용 알고리즘

  • 해싱

시간복잡도

  • $O(N)$

풀이

주어진 문자열이 팰린드롬인지 확인하는 간단한 문제인데… 문제는 메모리 제한이 너무 작아서 문자열 전체를 저장할 수 없습니다. 문자열의 길이가 입력으로 주어지지 않고 최대 $2 \times 10^7$인 것만 알고 있을 때, 메모리를 $4MB$ 이하만 사용해서 주어진 문자열이 팰린드롬인지 확인해야 합니다.

문자열을 저장할 수 없으면 해시값을 저장하면 됩니다. 두 가지 해시값을 저장할 건데, 하나는 해시값을 $f(s_0s_1\cdots s_{n-1}) = \sum s_iP^i$ 함수를 이용해 계산하고, 다른 하나는 $g(s_0s_1\cdots s_{n-1}) = \sum s_iP^{n-i-1}$을 이용합니다. 어떤 문자열 $S$가 팰린드롬인 것과 $f(S) = g(S)$인 것은 동치이므로 정수 2개만 이용해 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll P1 = 917, M1 = 998244353;
constexpr ll P2 = 119, M2 = 993244853;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N; char C;
    ll X1 = 1, X2 = 1, H11 = 0, H12 = 0, H21 = 0, H22 = 0;
    while(cin >> C){
        H11 = (X1 * C + H11) % M1;
        H12 = (H12 * P1 + C) % M1;
        H21 = (X2 * C + H21) % M2;
        H22 = (H22 * P2 + C) % M2;
        X1 = X1 * P1 % M1;
        X2 = X2 * P2 % M2;
    }
    if(H11 == H12 && H21 == H22) cout << "TAK";
    else cout << "NIE";
}