글 읽기 - 출력 초과가 나는데 이유를 모르겠습니다.

twinstar 6년 전 0

차라리 틀렸습니다가 뜨면 이해를 하겠는데 출력초과가 나와버려요...

#include <stdio.h>
#include <stdlib.h>
#include <cstdio>
#include <string.h>
#include <algorithm>

using namespace std;


char str[1000005];
int failure[1000005];
char pat[1000005];
int sav[1000005];

int cnt = 0;

int main()
{
	gets(str);
	gets(pat);
	int lens = strlen(str);
	int lenp = strlen(pat);
	int i = 0, j = 0;
	failure[0] = 0;

	for (j = 1; j < lenp; j++)
	{
		i = failure[j - 1];
		while ((pat[j] != pat[i + 1]) && (i > 0))
		{
			i = failure[i];

		}
		if (pat[j] == pat[i + 1])
			failure[j] = i + 1;
		else
			failure[j] = 0;

	}


	i = 0; j = 0;
	while (i < lens && j < lenp)
	{
		if (str[i] == pat[j])
		{
			i++;
			j++;
		}
		else if (j == 0) i++;
		else j = failure[j - 1];

		if (j == lenp)
		{
			sav[cnt] = i - lenp;
			j = failure[lenp - 1];
			i = sav[cnt] + failure[lenp - 1] + 1;
			cnt++;
		}
	}
	printf("%d\n", cnt);
	for (i = 0; i < cnt; i++)
	{
		printf("%d", sav[i] + 1);
		if (i < cnt - 1)
			printf(" ");
	}

}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

출력 초과가 나는데 이유를 모르겠습니다.

twinstar 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말