KMP 알고리즘

[devLupin]

• 어떠한 텍스트 t와 패턴 p가 주어졌을 때
• t 안에 p 패턴이 있는지 확인하는 방법
• 패턴 문자열 p의 접두사와 접미사의 일치 부분을 계산하는 failure 함수 이용
• 시간복잡도
  • 단순 탐색 : $O(T*P)$
  • KMP : $O(T+P)$

[devLupin]

• 단순히 있는지 없는지 판단할 때

#include <bits/stdc++.h>
using namespace std;

string t, p;
vector<int> f, ans;

void failure(string &s) {
    f.assign(s.size(), 0);
    int j = 0;
    for(int i = 1; i < s.size(); i++) {
        while(j > 0 && s[i] != s[j]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
}

bool solve() {
    int j = 0;
    for(int i = 0; i < t.size(); i++) {
        while(j > 0 && t[i] != p[j]) j = f[j-1];
        if(t[i] == p[j]) j++;
        if(j == p.size()) return 1;
    }
        return 0;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    getline(cin, t);
    getline(cin, p);

    failure(p);
    cout << solve() // 1이면 패턴이 존재하는 것.

    return 0;
}

[devLupin]

• 패턴의 개수 및 시작 위치를 찾고 싶을 때

#include <bits/stdc++.h>
using namespace std;

string t, p;
vector<int> f, ans;

void failure(string &s) {
    f.assign(s.size(), 0);
    int j = 0;
    for(int i = 1; i < s.size(); i++) {
        while(j > 0 && s[i] != s[j]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
}

void solve() {
    int j = 0;
    for(int i = 0; i < t.size(); i++) {
        while(j > 0 && t[i] != p[j]) j = f[j-1];
        if(t[i] == p[j]) j++;
        if(j == p.size()) {
            ans.push_back(i-j+1);
            j = f[j-1];  // 이후 다시 탐색해야 하므로, j-1로
        }
    }
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    getline(cin, t);
    getline(cin, p);

    failure(p);
    solve();

    cout << ans.size() << '\n';
    for(int x : ans) cout << x+1 << ' ';

    return 0;
}