글 읽기 - 시간초과 될만한부분좀 봐주세요.. ㅠ

minhas2 7년 전 0

첫번째 인덱스부터, 가장끝 인덱스부터 각각 원래 문자열의갯수만큼 비교해나가면서

문자열갯수 -=1을 해가면서 모든 문자가 일치하는 길이를 탐색하고

모든문자가 일치하면 가장처음,끝 범위를 제외한 나머지범위에서 길이만큼 비교하며 최종 문자열갯수를 카운팅한후 배열에 저장하게했습니다.

근데 시간초과가 자꾸떠서.. 뭐가 시간이많이잡혀먹은걸까요? ㅠㅠ

그냥 순차적으로 탐색하는것자체가 문제인가 싶었는데 그것외엔 방법이없는것같아서요 ㅠㅠ

뭐가문젤까요..?

#include <iostream>

using namespace std;
const int MAXSIZE = 100001;
const int M = -1;
const int P = 1;

bool compare(char*f, char* l, int& num, int origin_count, int& wordNum) {
	
	int lastchar_startIndex = origin_count - num;

	for (int i = 0 ,j=lastchar_startIndex; i < num; i++,j++) {
		if (f[i] != l[j]) return false;
	}
	if (num != origin_count) wordNum=2;
	if (num == origin_count) wordNum = 1;
	return true;
}

int CountingWord(int num,int origin_count,char* word,int* indexInform, int fwi) {
	int count = 0;

	int j = 0;
	int index = 0;
	for (int i = 0; i < fwi; i++) {
		index = indexInform[i];
		if (index + num >= origin_count) break;
		for (j = index; j < index + num; j++) {
			if (word[j - index] != word[j]) break;
		}
		if (j == index + num) count++;
	}

	return count;
}

int main()
{

	char *first_s = new char[MAXSIZE];
	char *last_s = new char[MAXSIZE];

	int count = 0;

	cin>>first_s;

	for (count = 0; first_s[count] !=NULL; count++) { last_s[count] = first_s[count]; }
	int num = count;
	int**saveResult = new int*[count];

	int wordNum = 0, resultIndex = 0;

	//첫문자의 인덱스저장
	int* saveFirstWordIndex = new int[count];
	int fwi = 0;

	for (int i = 1; i < count-1; i++) {
		if (first_s[i] == first_s[0]) {
			saveFirstWordIndex[fwi++] = i;
		}
	}

	while (num > 0) {
		if (compare(first_s, last_s, num, count,wordNum)) {

			wordNum += CountingWord(num, count, first_s,saveFirstWordIndex,fwi);
			saveResult[resultIndex] = new int[2];
			saveResult[resultIndex][0] = num;
			saveResult[resultIndex][1] = wordNum;
			resultIndex++;
		}
		num--;
	}
	printf("%d\n",resultIndex);

	for (int i = resultIndex - 1; i >= 0; i--)printf("%d %d\n", saveResult[i][0], saveResult[i][1]);

    return 0;
}

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

문제

문제

출처

ICPC

시간초과 될만한부분좀 봐주세요.. ㅠ

minhas2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말