[SOJ - 2652, 2307 - KMP] 계산 모드 가 원본 문자열 에 나타 난 횟수

char T[1000005];
char P[10005];
int next[10005];
void Get_Next(char *P)
{
	int TLength = strlen(P);
    next[0] = -1;
    int i = 0, j = -1;
	while (i < TLength) {
        if (j == -1 || P[i] == P[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else j = next[j];
    }
}
int ans;
void KMP_Matcher(char *T,char *P)
{
    int PLength = strlen(P);
    int TLength = strlen(T);
    int i, j = 0;
    for (i = 0; i < TLength; ) {
		while (i < TLength && j < PLength) {
			if (j == -1 || T[i] == P[j]) {
                ++i;
                ++j;
            } else j = next[j];
        }
        if (j == PLength) {
            ++ans;
            j = next[j];
        }
    }
    printf("%d
",ans);
}
int main()
{
    int n;
    scanf("%d", &n);
    getchar();
    while (n--) {
        ans = 0;
        gets(P);
        gets(T);
        Get_Next(P);
        KMP_Matcher(T, P);
    }
    return 0;
}

char T[1000005];
char P[10005];
int next[10005];
void Get_Next(char *P)
{
	int TLength = strlen(P);
    next[0] = -1;
    int i = 0, j = -1;
	while (i < TLength) {
        if (j == -1 || P[i] == P[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else j = next[j];
    }
}
int KMP_Matcher(char *T,char *P, int pos)
{
    int PLength = strlen(P);
    int TLength = strlen(T);
    int i = pos, j = 0;
    while (i < TLength && j < PLength) {
		if (j == -1 || T[i] == P[j]) {
			++i;
			++j;
		} else j = next[j];
	}
	if (j < PLength) return -1;
	else return i - j;
}