백준16854 편안한 문자열

작성일 | In

문제 링크

  • http://icpc.me/16854

사용 알고리즘

  • 해싱

시간복잡도

  • $O(N^2)$

풀이

어떤 부분 문자열이 올바른 괄호 문자열인지 판단하는 것은 간단합니다. 대칭 문자열인지 판단하는 방법을 알아봅시다.
정해는 어떤 똑똑한 방법을 이용하는 것으로 보이지만, 사실 해싱으로 간단하게 판별할 수 있습니다.

입력으로 들어온 문자열 $S$와 $S$를 뒤집은 문자열 $S’$의 해시를 전처리하면, 두 문자열의 특정 지점의 부분 문자열이 같은지 확인하는 것으로 대칭 문자열을 판별해낼 수 있습니다. 자세한 방법은 아래 코드를 참고해주세요.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;

template<ll P, ll M> struct Hashing {
    vector<ll> H, B;
    void build(const string &S){
        H.resize(S.size()+1);
        B.resize(S.size()+1);
        B[0] = 1;
        for(int i=1; i<=S.size(); i++) H[i] = (H[i-1] * P + S[i-1]) % M;
        for(int i=1; i<=S.size(); i++) B[i] = B[i-1] * P % M;
    }
    ll get(int s, int e){
        ll res = (H[e] - H[s-1] * B[e-s+1]) % M;
        return res < 0 ? res + M : res;
    }
};

Hashing<11, 998244353> H1, H3;
Hashing<9, 1000000007> H2, H4;

int N;
string S, T;

bool Check(int s, int e){
    if(H1.get(s, e) != H3.get(N-e+1, N-s+1)) return false;
    return H2.get(s, e) == H4.get(N-e+1, N-s+1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> S; T = S; N = S.size();
    H1.build(S); H2.build(S);
    reverse(all(T));
    for(auto &c : T) c = c == '(' ? ')' : '(';
    H3.build(T); H4.build(T);
    S = "#" + S;

    int res = 0;
    for(int i=1; i<=N; i++){
        int now = 0;
        for(int j=i; j<=N; j++){
            if(S[j] == '(') now++;
            else if(--now < 0) break;
            if(now == 0) res += Check(i, j);
        }
    }
    cout << res;
}