Password(CodeForces-126B)(KMP算法变形,字符串Dp，Hash)

前言

这里的Dp定义很容易和KMP的Fail数组搞混…

题目

传送门:
CodeForces
Vjudge
题目大意:
你现在有一个长度为n的字符串S,现在让你求它的一个最长子串T使其既为S前缀,又为S后缀,并且在S中非前缀非后缀中出现过一次
数据范围:
$1\le n\le 10^6$

思路

思路很简单,定义:
$Dp[i]为i为末尾的子串的后缀与能够匹配的整个串S的最长的前缀的位置$
没有时为-1
令$j$一开始等于$Dp[i?1]$,然后$j=Dp[j]$不断迭代至-1
显然,这个过程中在不断找i为末尾的子串的后缀如果$s[j+1]==s[i]$,那么$Dp[i]=j+1$
有人会说,这不是跟KMP中Fail数组一模一样吗？我们来看看：
这是Fail函数:

void GetFail(char *s){
    int len=strlen(s),i=1,j=0;Fail[0]=-1,Fail[1]=0;while(i<len){
    if(j==-1||s[j]==s[i]) Fail[++i]=++j;else j=Fail[j];}return ;
}

这是这道题Dp:

void CalDp(char *s){
    int len=strlen(s);memset(Dp,-1,sizeof(Dp));for(int i=1;i<len;i++){
    int j=Dp[i-1];while(j!=-1&&s[j+1]!=s[i]) j=Dp[j];if(s[j+1]==s[i]) Dp[i]=j+1;}return ;
}

输出来的样子：

所以Fail函数只适用于KMP,是为了快速找到下一个可能和主串中S匹配的字符的位置
而Dp[i]为i为末尾的子串的后缀与能够匹配的整个串S的最长的前缀的位置
所以两个不一样.
那么现在我们就可以找到一个位置$i\in [1,n?1)$判断它的最长后缀是否在S中有前缀.然后我们把$i\in [1,n)$的Dp[i]值全部在Hash中标记一下,代表出现过。
然后我们对于Dp[n-1],也就是串S的后缀不断令$i=Dp[i]$,只要它的Dp[i]在Hash中出现,那么就可以直接输出答案了.
注意边界时Dp[i]=-1或者i=-1

代码

#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<climits>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
int read(){
    int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return f*x;
}
#define INF 0x3f3f3f3f
#define MAXN 1000000
int Dp[MAXN+5];
char T[MAXN+5];
bool Hash[MAXN+5];
void CalDp(char *s){
    int len=strlen(s);memset(Dp,-1,sizeof(Dp));for(int i=1;i<len;i++){
    int j=Dp[i-1];while(j!=-1&&s[j+1]!=s[i]) j=Dp[j];if(s[j+1]==s[i]) Dp[i]=j+1;}return ;
}
int main(){
    scanf("%s",T);CalDp(T);int n=strlen(T);for(int i=1;i<n-1;i++)Hash[Dp[i]+1]=1;int x=n-1;while(x!=-1&&!Hash[Dp[x]+1]) x=Dp[x];if(x==-1||Dp[x]==-1){
    puts("Just a legend");return 0;}for(int i=0;i<=Dp[x];i++)printf("%c",T[i]);puts("");return 0;
}