글 읽기 - KMP 사용했는데 시간초과가 납니다 도와주세요

skesswswkk 3년 전 0

어느 부분을 더 고민해 봐야 하는 건가요?

#include <iostream>
#include <deque>
using namespace std;

deque<int> getPi(deque<int> p) {
	deque<int> Pi(p.size(), 0);
	int j = 0;
	for (int i = 1; i < p.size(); ++i) {
		while (j > 0 && p[i] != p[j]) {
			j = Pi[j - 1];//동일
		}
		if (p[i] == p[j]) {
			Pi[i] = ++j;
		}
	}

	return Pi;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	deque<int> dq;
	for (int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		dq.push_back(a);
	}

	int cnt = 0;
	int maxx = 0;
	bool flag = 0;

	while(1) {
		//종료조건
		if (dq.size() == maxx) {
			break;
		}

		deque<int> Pi = getPi(dq);
		int anss = Pi[dq.size() - 1];
		if (maxx < anss) {
			maxx = anss;
			cnt = 1;
			flag = 1;
		}
		else if (maxx == anss && maxx != 0) cnt++;

		dq.pop_front();
	}

	if (flag == 0) cout << -1 << "\n";
	else cout << maxx << " " << cnt << "\n";
}

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

문제

문제

출처

ICPC

KMP 사용했는데 시간초과가 납니다 도와주세요

skesswswkk 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말