글 읽기 - 답은 맞는데 시간초과가 계속 나네요...ㅠㅠ

jack2020 5년 전 0

테스트케이스는 맞구 "KMP" 알고리즘을 쓴 것도 맞습니다만...

계속해서 3퍼 대에서 시간초과가 나네요...

도와주세요! ㅠㅠㅠ

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

char T[1000005];
char P[1000005];
int keys[1000005];
vector<int> position;

void key(char *P) {
	int j = 0;
	for (int i = 1; i <= (int) strlen(P) - 1; i++) {
		while (j > 0 && P[i] != P[j]) {
			j = keys[j - 1];
		}
		if (P[i] == P[j]) {
			keys[i] = ++j;
		}
	}
	return;
}

void KMP(char *T, char *P) {
    int n = (int) strlen(T), m = (int) strlen(P), j = 0;
    for (int i = 0; i < n; i++) {
    	while (j > 0 && T[i] != P[j]) {
    		j = keys[j - 1];
    	}
    	if (T[i] == P[j]) {
    		if (j == m - 1) {
    			position.push_back(i - m + 2);
    		} else {
    			j++;
    		}
    	}
    }
    return;
}

int main() {
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin.getline(T, sizeof(T));
    cin.getline(P, sizeof(P));
	key(P);
	KMP(T, P);
	cout << (int) position.size() << "\n";
	for (int i = 0; i <= (int) position.size() - 1; i++) {
		cout << position[i] << " ";
	}
	return 0;
}

jh05013 5년 전 0

14줄을 잘 보세요.

jack2020 5년 전 0

14줄에는....잘 모르겠습니다 ㅠㅠ 이상이 없는 것 같은데요?

jh05013 5년 전 2

strlen을 for 조건 안에 넣으면 저 조건을 검사할 때마다 strlen을 다시 실행합니다. 그런데 strlen이 O(N)이 걸리므로 전체 for루프는 O(N^2)이 됩니다.

jack2020 5년 전 0

감사합니다 ㅠㅠ

근데 또 다른 문제가 생겼습니다...틀렸답니다 ㅋㅋ큐ㅠㅠㅠㅠ

한 번만 더 도와주시면 감사드리겠습니다 ㅠㅠ

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

문제

문제

출처

ICPC

답은 맞는데 시간초과가 계속 나네요...ㅠㅠ

jack2020 5년 전 0

jh05013 5년 전 0

jack2020 5년 전 0

jh05013 5년 전 2

jack2020 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말