5555 반지

#include <stdio.h>
#include <string.h>
 
int isStr(char* ring, char* str) {
    int lenR = strlen(ring);
    int lenS = strlen(str);
 
    for (int i = 0; i < lenR; i++) {
        int j = 0, st = i;
        if (ring[st] == str[0]) {
            for (j = 1; j < lenS; j++) {
                if (st + j == lenR) {
                    st = -j;
                }
                if (ring[st + j] != str[j]) {
                    break;
                }
            }
        }
        if (j == lenS)
            return 1;
    }
    return 0;
}
 
int main() {
    char str[105] = { 0 };
    scanf("%s", &str);
 
    int n;
    scanf("%d", &n);
 
    int sum = 0;
    while (n--) {
        char ring[105] = { 0 };
        scanf("%s", &ring);
 
        sum += isStr(ring, str);
    }
    printf("%d", sum);
}

KMP 알고리즘을 굳이 사용하지 않아도 해결 가능.

시간복잡도 N^2 였지만, input값이 작아서 시간 내 해결 가능.

끝부분을 다시 첫 부분으로 만드는 과정이 핵심.