12780번: 원피스

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


$O(l_hl_n)$

#include<cstdio>
#include<cstring>
char h[100001], n[11];
char *p;
int r;
int main() {
    scanf("%s%s", h, n);
    p = h;
    while (p = strstr(p, n)) p++, r++;
    printf("%d", r);
    return 0;
}

$O(l_h+l_n)$

kmp 알고리즘을 쓴다.

#include<cstdio>
char h[100001], n[11];
int pi[11] = { -1 }, r;
int main() {
    scanf("%s%s", h, n);
    for (int i = 0, j = -1; n[i];) {
        if (j == -1 || n[i] == n[j]) pi[++i] = ++j;
        else j = pi[j];
    }
    for (int i = 0, j = 0; h[i];) {
        if (j == -1 || h[i] == n[j]) ++i, r += !n[++j];
        else j = pi[j];
    }
    printf("%d", r);
    return 0;
}