글 읽기 - 카멜레온 부분 문자열 Z알고리즘

Coxie 5년 전 0

틀렸습니다가 뜨는데, 많은 예제를 만들어서 직접 돌려봤지만, 반례를 찾지 못했습니다.

aaa -> a

abababa -> aba

levelevelevel -> level

lllllllll -> lllllll

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int Z[(int)1e6+100], L, R;
int main(void)
{
	string S;
	cin >> S;
	int N = S.size();
	if (N < 3)
	{
		cout << -1;
		return 0;
	}
	for (int i = 1; i < N; ++i)
	{
		if (i > R)
		{
			L = R = i;
			while (R < N && S[R - L] == S[R]) ++R;
			Z[i] = R - L; R--;
			continue;
		}
		int k = i - L;
		if (Z[k] < R - i + 1) Z[i] = Z[k];
		else
		{
			L = i;
			while (R < N&&S[R - L] == S[R]) ++R;
			Z[i] = R - L; --R;
		}
	}
	sort(Z, Z + N);
	if (Z[N-2]) cout << S.substr(0, Z[N-2]);
	else cout << -1;
	return 0;
}

cpp05013 5년 전 4

abbababbbababaaaba

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

문제

문제

출처

ICPC

카멜레온 부분 문자열 Z알고리즘

Coxie 5년 전 0

cpp05013 5년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말