文章目录

前言题目思路代码

前言

这里的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; }