프양연 단어가 등장하는 횟수

1. 풀이 정리 2. 예외 사항 및 설계 완료 3. 풀이 -> 코딩

#include <stdio.h> #define MAX_N 10 #define MAX_S 10 //#define MAX_N 500010 //#define MAX_S 100010 char b[MAX_N], s[MAX_S]; int fail[MAX_S]; void make_fail_func() { fail[0] = 0; int j = 0; for (int i = 1; s[i] != '\0'; i++) { while (j > 0 && s[i] != s[j]) j = fail[j - 1]; if (s[i] == s[j]) fail[i] = ++j; else fail[i] = 0; } } int main() { freopen("input.txt", "r", stdin); int T; scanf("%d", &T); for (int tc = 1; tc <= T; tc++) { scanf("%s", b); scanf("%s", s); make_fail_func(); int j = 0; int cnt = 0; for (int i = 0; b[i] != '\0'; i++) { while (j > 0 && b[i] != s[j]) j = fail[j - 1]; if (b[i] == s[j]) { j++; if (s[j] == '\0') { j = fail[j - 1]; cnt++; } } } printf("#%d %d\n", tc, cnt); } }