글 읽기 - 도와주세요 고수님들 도무지 반례가 뭔지 모르겠습니다.ㅠㅠ

pda_pro12 5년 전 0

KMP로 접두사 접미사 일치하는 부분들의 길이를 측정해서 테이블에 저장해두고

뒤에서부터 그 길이를 측정하면서 최장 길이를 계산하였습니다만

반례가 어떤게 있을지 모르겠습니다...ㅠㅠ

#include<iostream>
#include<vector>
#include<string>

using namespace std;

vector<int> makeTable(string pattern) {
	int patternSize = pattern.size();
	vector<int> table(patternSize, 0);
	int j = 0;
	for (int i = 1; i < patternSize; i++) {
		while (j > 0 && pattern[i] != pattern[j]) {
			j = table[j - 1];
		}
		if (pattern[i] == pattern[j]) {
			table[i] = ++j;
		}
	}
	return table;
}

int main() {
	string pattern; int n;
	cin >> pattern >> n;
	vector<int> table = makeTable(pattern);
	int pivot = table[table.size() - 1], idx = table.size() - 1;
	bool res = false;
	if (pivot) res = true;
	for (int i = table.size() - 2; i >= 0; i--) {
		if (table[i] && table[i] == pivot - 1) {
			idx = i;
			res = true;
			pivot = table[i];
			continue;
		}
		else {
			break;
		}
	}
	//cout << res;
	long long a, b;
	a = table.size() + idx*(n - 1);
	b = table.size()*n;
	if (res)
		cout << a << '\n';
	else
		cout << b << '\n';
	return 0;
}

sait2000 5년 전 0

idx*(n - 1)에서 overflow가 날 것 같은데요.

pda_pro12 5년 전 0

long long인데 overflow발생할수 있나요?

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

문제

문제

출처

ICPC

도와주세요 고수님들 도무지 반례가 뭔지 모르겠습니다.ㅠㅠ

pda_pro12 5년 전 0

sait2000 5년 전 0

pda_pro12 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말