백준3308 Matching

작성일 | In

문제 링크

  • http://icpc.me/3308

문제 출처

  • 2011 CEOI Day1 2번

사용 알고리즘

  • KMP
  • 세그먼트 트리

시간복잡도

  • $O((N+K) \log K)$

풀이

문자열 $A_i = H_i$에서 패턴 $P_i = S^{-1}_i$를 찾는 문제입니다.
부분 문자열과 패턴이 완전히 일치하는 경우 뿐만 아니라, 좌표 압축한 결과가 같을 때도 매칭시킵니다.

KMP를 적용할 수 있다는 생각이 듭니다.
두 문자가 같은지 확인하는 것 대신, 두 원소가 문자열에 각각 추가되었을 때 서로 자신보다 작은 원소의 개수와 큰 원소의 개수가 각각 같은지(등수가 같은지) 확인하면 됩니다. 등수가 같은지 확인하는 것은 Segment Tree나 Fenwick Tree 등의 자료구조로 쉽게 확인할 수 있습니다.

전체 코드

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#pragma GCC optimize ("O3")
#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;

typedef long long ll;

struct BIT{
    static const int S = 1 << 20;
    int tree[S];
    void clear(){ memset(tree, 0, sizeof tree); }
    void update(int x, ll v){ for(x++; x<S; x+=x&-x) tree[x] += v; }
    int query(int x){ ll ret = 0; for(x++; x; x^=x&-x) ret += tree[x]; return ret; }
    int query(int s, int e){ return query(e) - query(s-1); }
} bit;
void vec_compress(vector<int> &vec){
    vector<int> comp; comp.reserve(vec.size());
    for(auto i : vec) comp.push_back(i);
    compress(comp);
    for(auto &i : vec) i = IDX(comp, i) + 1;
}

int n, k;
vector<int> str, pat, tmp;

vector<int> fail, le, ri;
void get_fail(){
    fail.resize(k);
    le.resize(k);
    ri.resize(k);

    bit.clear();
    for(int i=0; i<pat.size(); i++){
        bit.update(pat[i], 1);
        le[i] = bit.query(1, pat[i]-1);
        ri[i] = bit.query(pat[i]+1, k);
    }

    bit.clear();
    function<bool(int, int)> match = [&](int i, int j){
        return le[j] == bit.query(1, pat[i]-1) && ri[j] == bit.query(pat[i]+1, n);
    };
    for(int i=1, j=0; i<pat.size(); i++){
        while(j && !match(i, j)){
            for(int s=i-j; s<i-fail[j-1]; s++) bit.update(pat[s], -1);
            j = fail[j-1];
        }
        if(match(i, j)){
            bit.update(pat[i], 1);
            fail[i] = ++j;
        }
    }
}

vector<int> kmp(){
    vector<int> ret;
    get_fail(); bit.clear();
    function<bool(int, int)> match = [&](int i, int j){
        return le[j] == bit.query(1, str[i]-1) && ri[j] == bit.query(str[i]+1, n);
    };
    for(int i=0, j=0; i<str.size(); i++){
        while(j && !match(i, j)){
            for(int s=i-j; s<i-fail[j-1]; s++) bit.update(str[s], -1);
            j = fail[j-1];
        }
        if(match(i, j)){
            if(j+1 == pat.size()){
                ret.push_back(i-j);
                for(int s=i-j; s<i-fail[j]+1; s++) bit.update(str[s], -1);
                j = fail[j];
            }
            else j++;
            bit.update(str[i], 1);
        }
    }
    return move(ret);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> k >> n; pat.resize(k); iota(all(pat), 0);
    tmp.resize(k); for(auto &i : tmp) cin >> i;
    str.resize(n); for(auto &i : str) cin >> i; vec_compress(str);
    sort(all(pat), [](int a, int b){ return tmp[a] < tmp[b]; });
    for(auto &i : pat) i++;
    auto res = kmp();
    cout << res.size() << "\n";
    for(auto i : res) cout << i+1 << " ";
}