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; }