1786번: 찾기

https://www.acmicpc.net/problem/1786

kmp 알고리즘을 구현한다.

시간복잡도는 $O(n+m)$

#include<cstdio>
#include<vector>
using namespace std;
char t[1000001], p[1000001];
int pi[1000001] = { -1 };
vector<int> res;
int main() {
    scanf("%[^\n]%*c%[^\n]", t, p);
    for (int i = 0, j = -1; p[i]; pi[++i] = ++j) while (~j && p[i] ^ p[j]) j = pi[j];
    for (int i = 0, j = 0; t[i]; i++) {
        while (~j && t[i] ^ p[j]) j = pi[j];
        if (!p[++j]) res.push_back(i + 2 - j);
    }
    printf("%d\n", res.size());
    for (int it : res) printf("%d ", it);
    return 0;
}