1543번: 문서 검색

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


$O(ab)$ a, b: 문서, 단어 문자열 길이

앞에서부터 단어가 있으면 카운트하고 그 길이만큼 건너뛴다.
이는 그리디 알고리즘인데 건너뛰는 부분에 단어가 있어도 이것을 포함하는 해보다 항상 나쁘지 않기 때문에 쓸 수 있다.

#include<cstdio>
#include<cstring>
char s[2501], c[51];
int r, sl, cl;
int main() {
    scanf("%[^\n] %[^\n]", s, c);
    sl = strlen(s);
    cl = strlen(c);
    for (int i = 0; i < sl; i++) if (!strncmp(s + i, c, cl)) r++, i += cl - 1;
    printf("%d", r);
    return 0;
}