글 읽기 - 반례좀 찾아주시면 감사하겠습니다

yg4236 4년 전 0

예시를 제가 생각해서 써보면 다맞는데 틀린예시좀 집어주시면 감사하겠습니다ㅠㅠ

#define _CRT_SECURE_NO_WARNINGS
#define MAX 1000001
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int failure[MAX] = { 0, };

void fail(char* pat)
{
	int i, j;
	int n = strlen(pat);
	failure[0] = -1;

	for (j = 1;j < n;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] = -1;
	}

}

int main()
{
	char* t;
	char* p;
	t = (char*)malloc(sizeof(char) * MAX);
	p = (char*)malloc(sizeof(char) * MAX);
	fgets(t, MAX, stdin);
	fgets(p, MAX, stdin);

	fail(p);
	int i = 0;
	int j = 0;
	int lens = strlen(t) - 1;
	int lenp = strlen(p) - 1;
	int cnt = 0;
	int index[10] = { 0, };
	
	while (i < lens && j < lenp)
	{
		if (t[i] == p[j])
		{
			i++;
			j++;
		}
		else if (j == 0) i++;
		else
			j = failure[j - 1] + 1;
		if (j == lenp)
		{
			index[cnt]=i - lenp;
			cnt++;
			j = 0;
			i--;
		}
	}
	printf("%d\n",cnt);
	for(i=0;i<cnt;i++)
	{
		printf("%d\n", index[i]+1);
	}
	
	free(t);
	free(p);
	return 0;
}

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

문제

문제

출처

ICPC

반례좀 찾아주시면 감사하겠습니다

yg4236 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말