Решение задачи Пароль с Codeforces

Без пояснения   Просмотров: 17


Астерикс, Обеликс и их временные спутники Суффикс и Префикс наконец нашли храм Гармонии. Однако его двери были прочно заперты, и даже Обеликсу было не под силу их открыть.

Чуть позже они обнаружили строку s, которая была высечена в камне над воротами храма. Астерикс предположил, что это пароль для входа в храм, и громко вслух произнес эту надпись. Однако ничего не произошло. Тогда Астерикс предположил, что паролем является некоторая подстрока t строки s.

Префикс считал, что строка t является началом строки s. Суффикс считал, что строки t должна быть концом строки s. Обеликс же посчитал, что t должна находиться где-то внутри строки s, то есть не являться ни ее началом, ни ее концом.

Астерикс выбрал подстроку t так, чтобы угодить всем своим спутникам. Кроме того, из всех допустимых вариантов Астерикс выбрал наиболее длинный (потому что Астерикс любит длинные строки). Когда Астерикс произнес строку t — двери храма открылись.

Вам известна строка s. Найдите строку t или определите, что таких строк не существует, а все написанное выше — всего лишь легенда.

Код

#include <bits/stdc++.h>

using namespace std;


const int MAXN = 1000 * 1000 + 60;

int f[MAXN], cnt[MAXN];
string s;

int main() {
	cin >> s;
	int x = 0;
	for (int i = 1; i < s.size(); i++) {
		while (x && s[x] != s[i])
			x = f[x - 1];
		if (s[x] == s[i])
			f[i] = ++x, cnt[x]++;
		else
			f[i] = 0;
	}
	if (f[s.size() - 1] && cnt[f[s.size() - 1]] > 1)
		cout << s.substr(0, f[s.size() - 1]);
	else {
		if (f[s.size() - 1] && f[f[s.size() - 1] - 1])
			cout << s.substr(0, f[f[s.size() - 1] - 1]);
		else
			cout << "Just a legend";
	}
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться