#include <cstdio>
#include <cstring>
#include <iostream>
#include <ctime>
using namespace std;
const int M = 3000005;
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,t1,t2,f[35],g[35],nx[M];char s[M];
void init()
{
	for(int i=2,j=0,p=1;i<=n;i++)
	{
		j=max(min(nx[i-p+1],p+nx[p]-i),0);
		while(i+j<=n && s[i+j]==s[j+1]) j++;
		nx[i]=j;
		if(p+nx[p]<i+nx[i]) p=i;
	}
	nx[1]=n;
}
int cmp(int x,int r)// compare [x...r] and [1...]
{
	if(x+nx[x]-1>=r) return 0;
	return s[nx[x]+1]<s[x+nx[x]]?1:-1;
}
int get(int x,int y,int r)// x>y compare [x..r] and [y..r]
{
	int t=0;
	if(t=cmp(y+r-x+1,r)) return t>0?x:y;
	if(t=cmp(r-x+2,y-1)) return t>0?y:x;
	return y;
}
signed main()
{
	scanf("%s",s+1);n=strlen(s+1);
	init();
	for(int i=1;i<=n;i++)
	{
		swap(f,g);swap(t1,t2);f[t1=1]=i;
		for(int j=1;j<=t2;j++) while(t1)
		{
			int x=g[j],y=f[t1];
			//x is useless
			if(s[x+(i-y)]>s[i]) break;
			//can't distinguish them
			if(s[x+(i-y)]==s[i])
			{
				//y is useless
				if((i-y+1)*2>i-x+1) t1--;
				f[++t1]=x;break;
			}
			//y is useless
			t1--;if(!t1) {f[++t1]=x;break;}
		}
		int ans=f[1];
		for(int j=2;j<=t1;j++)
			ans=get(ans,f[j],i);
		printf("%d ",ans);
	}
}

P5334 [JSOI2019] 节日庆典 题解

本题解的侧重点在于对一些代码中难懂的细节加以说明。欢迎各位大佬指正。

前置知识：扩展 KMP，最小表示法的定义（本题解中并不需要了解最小表示法的求解过程）。

第一部分：预选数组

在这道题中，对于每一个 $i\in[1,n]$，暴力枚举 $1 \sim i$ 中的每一个字母去判断，时间复杂度肯定是不能接受的，因此考虑引入预选数组 $cur$，来统计可能的答案。

对于预选数组中存放的下标而言，对于任意两个元素 $x$ 和 $y$，满足 $S[x,i]$ 的字典序 大致等于 $S[y,i]$ 的字典序。

这里，大致等于 的意思是 非严格 小于。举个例子，设三个字符串 $A=\texttt{aaac}$，$B=\texttt{aaa}$，$C=\texttt{aac}$，其中，$A$ 和 $B$ 字符串的字典序大致相等，而 $A$ 字符串的字典序严格小于 $C$ 字符串。

考虑如何计算 $cur$ 数组。

容易发现一个性质：如果上一次的 $cur$ 数组中，元素 $j$ 被删除，则这个元素不会再在未来的 $cur$ 数组中出现。

根据上方的性质，我们首先，先将 $i$ 一个一个放入 $cur$ 数组中。然后，枚举每一个上一次 $cur$ 数组中的元素 $j$。同时，新定义一个 $nex$ 数组，表示当前情况下的预选数组。对于每一个 $j$ 而言，都去遍历 $nex$ 中的每一个元素。设当前枚举到 $nex$ 数组中的元素 $k$。根据 大致等于 的定义，我们对 $S[k,i-j+k]$ 和 $S[j,i]$ 进行比较。这里有一个巧妙的地方，由于 $i$ 在不断向后移动，留在 $cur$ 数组中的元素的 $j$ 到 $i-1$ 个字符已经进行过比较，因此每次的比较不需要逐一比较，只需要去比较 $S[i-j+k]$ 和 $S[i]$ 即可（对于不理解这个地方的读者，笔者建议可以自己去手动模拟一下）。

比较 $S[i-j+k]$ 和 $S[i]$ 有三种情况：

• 若 $S[i-j+k]$ 等于 $S[i]$，则说明两字符串大致相等。

• 若 $S[i-j+k]$ 小于 $S[i]$，则说明字符串 $S[j,i]$ 字典序严格大于 $S[k,i-j+k]$，此时字符串 $S[j,i]$ 不能加入 $nex$ 数组。

• 若 $S[i-j+k]$ 大于 $S[i]$，则说明字符串 $S[k,i-j+k]$ 字典序严格大于 $S[j,i]$，此时字符串 $S[k,i-j+k]$ 踢出 $nex$ 数组。继续枚举 $nex$ 数组中的其它元素。

这一部分代码如下：

for(int i=1;i<=n;i++)
{
	cur.push_back(i),nex.clear();
	for(int j:cur)
	{
		bool flag=1;
		while(!nex.empty())
		{
			int k=nex.back();
			if(s[i-j+k]==s[i])	break ;
			else if(s[i-j+k]<s[i])	
			{
				flag=0;
				break ;
			}
			nex.pop_back();
        }
    }
}

第二部分：对于预选数组的优化

如果按照这种规则插入到预选数组的话，势必还是会超时，考虑优化预选数组中的元素数量。

我们来推理一个性质，对于预选数组中的两个元素 $i$ 和 $j$，若满足 $|j|<|i|<2 \times |j|$，则 $j$ 一定不是最优解（$|j|$ 表示字符串 $S[j,r]$ 的长度，$r$ 为当前枚举字符串 $S$ 前缀的长度）。

证明：我们令 $S[i,r]=A+A+B$，$S[j,r]=A+B$。同时，我们定义字符串 $S[k,r]=B$，且 $A$ 和 $B$ 均为字符串。

设 $lena$ 表示字符串 $A$ 的长度，$lenb$ 表示字符串 $B$ 的长度，分以下两类情况讨论：

① $lena>lenb$，因为预选数组中的字符串字典序大致相等，因此此时字符串 $B$ 一定是 $A$ 的前缀。

• 若 $A[lenb+1]$ 小于 $S[1]$，则此时以 $i$ 开头的字符串的字典序一定小于以 $j$ 开头的。

• 若 $A[lenb+1]$ 大于 $S[1]$，则此时以 $k$ 开头的字符串一定比以 $j$ 开头的字典序小。

于是我们得到，当 $lena>lenb$ 时，以 $j$ 开头的字符串一定不是唯一最优解。

② $lena<lenb$，此时又分为以下两种情况：

• 若 $B[lenb-lena+1]$ 小于 $S[1]$，则此时以 $i$ 开头的字符串的字典序一定小于以 $j$ 开头的。

• 若 $B[lenb-lena+1]$ 大于 $S[1]$，则此时以 $k$ 开头的字符串一定比以 $j$ 开头的字典序小。

于是我们又得到，当 $lena<lenb$ 时，以 $j$ 开头的字符串一定不是唯一最优解。

综上所述，当 $i$ 和 $j$ 满足 $|j|<|i|<2 \times |j|$ 时，以 $j$ 开头的字符串一定不是唯一最优解。

我们考虑用刚刚代码中的字母去替换以上不等式，化简后得到如下不等式：$0<j-k<i-j$。

其中，$j-k>0$ 这个条件显然成立，则不等式可简化为 $j-k<i-j$，则说明当 $j-k<i-j$ 时，以 $j$ 开头的字符串一定不是唯一最优解。故在元素 $j$ 加入 $nex$ 数组时，判断 $i-j \le j-k$ 即可。

这一部分代码如下：

  if(flag and (nex.empty() or i-j<=j-nex.back()))	nex.push_back(j);

第三部分：计算答案

枚举每一个预选数组中的元素，去逐位比较字符串中的字母来计算字典序大小，但这样，刚刚优化下来的时间又被提上去了，考虑优化。

逐位比较显然就是最浪费时间的一个部分，从这个方面入手去优化。

我们将预选数组中的元素 $x$ 和 $y$ 的字符串表示出来如下：

$S[x]=S[x,r]+S[1,x-1]$，$S[y]=S[y,r]+S[1,y-1]$。

根据预选数组的条件，我们可以知道，$S[y,r]$ 一定是 $S[x,r]$ 的一个严格前缀，于是这部分无需比较。此时要比较的是 $S[x+r-y+1,r]+S[1,x-1]$ 和 $S[1,y-1]$。

发现 $S[x+r-y+1,r]$ 和 $S[1,y-1]$ 正好对应了字符串 $S$ 的后缀和开头，字符串相同的部分无需比较，因此只需要找到第一个不同的位置即可。使用扩展 KMP 算法即可。设最长公共前缀数组用 $lcp$ 表示，$x=x+r-y+1$，则要比较的位置就是 $S[x+lcp[x]]$ 和 $S[lcp[x]+1]$。

如果此时 $x$ 字符串剩余的后缀与 $y$ 字符串的前缀相同，则 $y$ 字符串要比较的部分变为 $S[1+r-x+1,y-1]$，$x$ 字符串要比较的部分变为 $S[1,x-1]$。此时又如同上方后缀和开头的关系，令 $y=1+r-x+1$，所以要比较的部分就是 $S[lcp[y]+1]$ 和 $S[y+lcp[y]]$。

如果以上两者均相同，因为要输出较小的 $i$，所以 $cmp$ 函数应该返回 $true$，表示保留当前的答案。

这一部分代码如下：

bool cmp(int x,int y,int r)
{
    int t=x-1,w=y-1;
	x=(x+r-y)+1;y=1;
	if(x+lcp[x]<=r)	return s[x+lcp[x]]<s[lcp[x]+1];
	y=(y+r-x)+1;
	if(y+lcp[y]<=w and lcp[y]+1<=t)	return s[lcp[y]+1]<s[y+lcp[y]];
	return 1;
}//比较函数

cur=nex;
ans=cur[0];
for(int j:cur)	ans=cmp(ans,j,i)?ans:j;
cout<<ans<<" ";

最后，完整代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;
const int N=3e6+10;

int n,lcp[N],ans;
string s;
vector<int>cur,nex;

void exkmp()
{
	int a=1,k=0,len=s.size();
	lcp[0]=len;
	while(s[k]==s[k+1] and k+1<len)	k++;
	lcp[1]=k;
	for(int i=2;i<len;i++)
	{
		if(lcp[i-a]+i<lcp[a]+a)
		{
			lcp[i]=lcp[i-a];
		}
		else
		{
			int j=lcp[a]+a-i;
			if(j<0)	j=0;
			while(i+j<len and s[i+j]==s[j])	j++;
			lcp[i]=j;
			a=i;
		}
	}
}

bool cmp(int x,int y,int r)
{
    int t=x-1,w=y-1;
	x=(x+r-y)+1;y=1;
	if(x+lcp[x]<=r)	return s[x+lcp[x]]<s[lcp[x]+1];
	y=(y+r-x)+1;
	if(y+lcp[y]<=w and lcp[y]+1<=t)	return s[lcp[y]+1]<s[y+lcp[y]];
	return 1;
}

int main()
{
	cin>>s;
	n=s.size();
	exkmp();
	s=' '+s;
	for(int i=n;i>=1;i--)	lcp[i]=lcp[i-1];
	for(int i=1;i<=n;i++)
	{
		cur.push_back(i),nex.clear();
		for(int j:cur)
		{
			bool flag=1;
			while(!nex.empty())
			{
				int k=nex.back();
				if(s[i-j+k]==s[i])	break ;
				else if(s[i-j+k]<s[i])	
				{
					flag=0;
					break ;
				}
				nex.pop_back();
			}
			if(flag and (nex.empty() or i-j<=j-nex.back()))	nex.push_back(j);
		}
		cur=nex;
		ans=cur[0];
		for(int j:cur)	ans=cmp(ans,j,i)?ans:j;
		cout<<ans<<" ";
	}
	return 0;
}

这篇题解到此结束，感谢大家阅读这篇题解。