글 읽기 - KMP로 풀어봤는데 99%에서 틀립니다 어디가 틀렸는지 도와주십쇼 ㅜ

isvara 4년 전 0

i번째에서 시작하는 pi를 구해서 pi의 값중 가장 큰값을 찾도록 구현했습니다..어떤 반례가 있을까요 ..??

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

string s;

vector<int> getPi(string p) {  
	int m =(int)p.size();
	vector<int>pi(m, 0);
	int j = 0;
	for (int i = 1; i < m; 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::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> s;
	int ans = 0;
	
	for (int i = 0; i < s.size(); i++) {
		string substr = s.substr(i, s.size());
		vector<int>res=getPi(substr);
		
		for (int j = 0; j < res.size(); j++)
			ans = max(ans, res[j]);
	}
	if (ans == 0)
		cout << "1";
	else
		cout << ans;
}

kdr06006 4년 전 0

--> 0

일거같습니다

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

문제

문제

출처

ICPC

KMP로 풀어봤는데 99%에서 틀립니다 어디가 틀렸는지 도와주십쇼 ㅜ

isvara 4년 전 0

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말