글 읽기 - 최장 공통 부분 문자열 질문입니다

dmazpzp5526 9년 전 0

코딩 테스트에서 테스트케이스를 주면 0ms로 수행이 되는데

문제 정답제출하기 하면 시간초과로 오답처리가 납니다..

어디에 문제가 있을까요? 3중for문이 문제라면 정답에 관한 힌트좀 부탁드리겠습니다

#include <stdio.h>
#include <string.h>
#define MAX_LENGTH 200000
#define MAX(a,b) a > b ? a : b

int main()
{
	char str_1[MAX_LENGTH] = {0,}, str_2[MAX_LENGTH] = {0,};
	int temp_count = 0, count_max = 0, max_point;
	int str_1_length;
	int str_2_length;

	scanf("%s", str_1);
	scanf("%s", str_2);

	str_1_length = strlen((char *) str_1);
	str_2_length = strlen((char *) str_2);

	for (int i = 0; i < str_1_length; i += (temp_count > 1 ? temp_count : 1)){
		for (int r = 0; r < str_2_length; r++){
			temp_count = 0;
			for (int x = 0; x < (MAX(str_1_length, str_2_length) - i); x++){
				if (str_1[i+x] == str_2[r+x])
					temp_count++;
				else
					break;
			}
			if (temp_count > count_max){
				count_max = temp_count;
				max_point = i;
			}
		}
	}

	printf("%d\n", count_max);

	for (int i = max_point; i < max_point + count_max; i++)
		printf("%c", str_1[i]);

	return 1;
}

hihihi 9년 전 1

문자열 길이의합이 최대 20만이므로 N^2 만 돌려도 시간초과가 납니다......

저는 suffix array를 이용했네요 !

Nada 9년 전 1

N으로 풀어야 되는 문제입니다

10^9 작업당 1초라고 생각하시면 됩니다

저는 hash로 풀었네요.

dmazpzp5526 9년 전 0

hihihi님 Nada님 감사합니다

다시 한번 풀어봐야겠습니다 ㅠㅠ

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

문제

문제

출처

ICPC

최장 공통 부분 문자열 질문입니다

dmazpzp5526 9년 전 0

hihihi 9년 전 1

Nada 9년 전 1

dmazpzp5526 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말