Codeforces Beta Round #93 (Div. 1 Only) B : Password

問題概要

長さL(<10^6)の文字列strが与えられる。strのsubstringで、strのprefixになっていてかつsuffixになっているような部分文字列がstrの内部に存在するならば出力する問題。

解法

Z-algorithmの練習。
Z-algorithmを適用して、Z[i]=L-iならばsuffixにもなっていることがわかる。後はそれより以前に長さL-i以上の値があったかどうかで判定できる。

acceptされたコード

計算量O(L)。

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_L = 1e6;
char str[MAX_L + 1];
int Z[MAX_L];

void z_algorithm(){
	const int L = strlen(str);

	for(int i=1, left=0, right=0; i<L; i++){
		if(i > right){
			left = right = i;
			for(;right < L && str[right-left] == str[right]; right++);
			Z[i] = right - left;
			right--;
		}
		else{
			int k = i - left;
			if(Z[k] < right - i + 1){
				Z[i] = Z[k];
			}
			else{
				left = i;
				for(;right < L && str[right-left] == str[right]; right++);
				Z[i] = right - left;
				right--;
			}
		}
	}
}

void init(){
	scanf("%[^\n]%*c", str);
}

void solve(){
	z_algorithm();
	const int L = strlen(str);
	int maxi = 0;
	for(int i=0; i<L; i++){
		if(Z[i] == L - i && maxi >= L - i){
			str[L - i] = '\0';
			puts(str);
			return ;
		}
		maxi = max(maxi, Z[i]);
	}

	puts("Just a legend");
}

int main(){
	init();
	solve();

	return 0;
}