Codeforces 126B Password（Z算法）

题意

给定一个字符串 \(s\) ，求一个子串 \(t\) 满足 \(t\) 是 \(s\) 的前缀、后缀且在除前缀后缀之外的地方出现过。

\(1 \leq |s| \leq 10^6\)

思路

\(\text{Z}\)算法是一个和 \(\text{Manacher}\)算法很像的字符串算法，功能是求出一个 \(z\) 数组，代表以 \(i\) 开头的后缀同整个串的 \(\text{lcp}\) 。

首先回顾一下 \(\text{Manacher}\)算法的流程。

int pos,r=0;

FOR(i,1,n)	//字符串Manacher是在原字符串每两字符间插入'#'的字符串。

{

	if(i<=r)p[i]=std::min(p[(pos<<1)-i],r-i+1);

	else p[i]=1;

	while(i-p[i]>=1&&i+p[i]<=n&&mnc[i-p[i]]==mnc[i+p[i]])p[i]++;

	if(chk_max(r,i+p[i]-1))pos=i;

}

\(\text{Manacher}\)算法通过维护了目前扫到的最有端点，使得复杂度变成线性（可以发现把第 \(3,4\) 行替换成 p[i]=1; ，就变成了 \(O(n^2)\) 的暴力。

把它稍微变一下，就变成了\(\text{Z}\)算法。

z[1]=n;

int l,r=0;

FOR(i,2,n)

{

	if(i<=r)z[i]=std::min(z[i-l+1],r-i+1);

	else z[i]=0;

	while(i+z[i]<=n&&str[i+z[i]]==str[1+z[i]])z[i]++;

	if(chk_max(r,i+z[i]-1))l=i;

}

仍然是通过最右端点保证复杂度，和 \(\text{Manacher}\)完全一个道理。

对于这道题目而言，先考虑既是前缀又是后缀的限制，只需要对原串 \(str\) 求一下 \(z\) 数组，如果一个位置 \(i\) 满足 \(z[i]=|str|-i+1\) ，那么 \([i,|str|]\) 这个串就既是前缀又是后缀了。至于这个串还得在不是前缀不是后缀的地方出现过，我们可以对 \(z\) 数组求一个前缀最大值（除了 \(z[1]\) ，\(z[1]\) 没什么意义），这个前缀最大值就代表出现过的最长的前缀，因为你需要的串 \([i,|str|]\) 肯定也是个前缀，所以就看 \(|str|-i+1\) 是不是小于等于前缀最大值即可。

代码

#include<bits/stdc++.h>

#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)

#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)

template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}

template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}

typedef long long ll;

const int N=1e6+5;

char str[N];int z[N];

int n;

void get_z(char *str,int n)

{

	z[1]=n;

	int l,r=0;

	FOR(i,2,n)

	{

		if(i<=r)z[i]=std::min(z[i-l+1],r-i+1);

		else z[i]=0;

		while(i+z[i]<=n&&str[i+z[i]]==str[1+z[i]])z[i]++;

		if(chk_max(r,i+z[i]-1))l=i;

	}

}

int main()

{

	scanf("%s",str+1);

	n=strlen(str+1);

	get_z(str,n);

	int r=0;

	FOR(i,2,n)

	{

		if(z[i]==n-i+1&&r>=n-i+1)

		{

			FOR(j,1,n-i+1)putchar(str[j]);

			return 0;

		}

		chk_max(r,z[i]);

	}

	puts("Just a legend");

	return 0;

}

巴特西

Codeforces 126B Password（Z算法）

题意

思路

代码

最新文章

热门文章