[文章目录]
Description
给定一个字符串S，与一个整数K，定义S的子串T=S(i, j)是关于第K位的识别子串，满足以下两个条件：
1、i≤K≤j。
2、子串T只在S中出现过一次。
例如，S="banana"，K=5，则关于第K位的识别子串有"nana"，"anan"，"anana"，"nan"，"banan"和"banana"。
现在，给定S，XX希望知道对于S的每一位，最短的识别子串长度是多少，请你来帮助他。长度<=5*10^5
就是找end_set大小为1的节点表示最短的子串的长度，即dep[pre]+1。
有了以每个位置结束的最短识别子串的长度其余的都好说。
对于在子串里的点的位数为当前长度，在当前子串前的位置，贡献为其到结束位置的长度，关于位置为一个递降等差序列。
维护的话，分开处理，等差序列那段直接从后向前递推即可，在子串内部的位置用堆以及线段树都是可以的。
1396
#include <queue>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
#define N 101000
char s[N];
int n,last=1,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],len[N],r[N];
bool vis[N<<1];
void insert(int x)
{
int p=last,cur=++tot;
last=cur,dep[cur]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
if(!p) pre[cur]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[cur]=q;
else
{
int clo=++tot;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
}
vector<int>ve[N];
priority_queue<int,vector<int>,greater<int> >he,del;
int main()
{
scanf("%s",s),n=strlen(s);
int i,j,p;
for(i=0;i<n;++i) insert(s[i]-'a');
for(i=1;i<=tot;++i) vis[pre[i]]=1;
memset(r,0x3f,sizeof(int)*(n+10));
for(p=1,i=0;i<n;++i) if(!vis[p=ch[p][s[i]-'a']])
len[i]=dep[pre[p]]+1,r[i-len[i]+1]=min(r[i-len[i]+1],len[i]);
for(i=n-1;i>=0;--i) r[i]=min(r[i+1]+1,r[i]);
for(i=0;i<n;++i) if(len[i]) ve[i-len[i]+1].pb(len[i]),ve[i+1].pb(-len[i]);
for(i=0;i<n;++i)
{
for(j=0;j<(int)ve[i].size();++j)
{
if(ve[i][j]>0) he.push(ve[i][j]);
else del.push(-ve[i][j]);
}
while(!he.empty()&&!del.empty()&&he.top()==del.top()) he.pop(),del.pop();
if(he.empty()) printf("%d\n",r[i]);
else printf("%d\n",min(r[i],he.top()));
}
return 0;
}
2865
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define pb push_back
#define N 501000
char s[N];
int n,M,last=1,tot=1,ch[N<<1][26],pre[N<<1],dep[N<<1],len[N],r[N],mi[N<<2];
bool vis[N<<1];
void insert(int x)
{
int p=last,cur=++tot;
last=cur,dep[cur]=dep[p]+1;
for(;p&&!ch[p][x];p=pre[p]) ch[p][x]=cur;
if(!p) pre[cur]=1;
else
{
int q=ch[p][x];
if(dep[q]==dep[p]+1) pre[cur]=q;
else
{
int clo=++tot;
memcpy(ch[clo],ch[q],sizeof(ch[q]));
dep[clo]=dep[p]+1,pre[clo]=pre[q],pre[q]=pre[cur]=clo;
for(;p&&ch[p][x]==q;p=pre[p]) ch[p][x]=clo;
}
}
}
void fix(int l,int r,int w)
{
l++,r++;
for(l=l+M-1,r=r+M+1;l^r^1;l>>=1,r>>=1)
{
if(~l&1) mi[l^1]=min(mi[l^1],w);
if(r&1) mi[r^1]=min(mi[r^1],w);
}
}
int query(int x)
{
int re=0x3f3f3f3f; x=x+M+1;
while(x) re=min(re,mi[x]),x>>=1;
return re;
}
int main()
{
scanf("%s",s),n=strlen(s);
int i,p;
for(i=0;i<n;++i) insert(s[i]-'a');
for(i=1;i<=tot;++i) vis[pre[i]]=1;
memset(r,0x3f,sizeof(int)*(n+10));
for(p=1,i=0;i<n;++i) if(!vis[p=ch[p][s[i]-'a']])
len[i]=dep[pre[p]]+1,r[i-len[i]+1]=min(r[i-len[i]+1],len[i]);
for(i=n-1;i>=0;--i) r[i]=min(r[i+1]+1,r[i]);
for(M=1;M<=(n+1);M<<=1);
memset(mi,0x3f,sizeof(int)*((M<<1)+10));
for(i=0;i<n;++i) if(len[i]) fix(i-len[i]+1,i,len[i]);
for(i=0;i<n;++i) printf("%d\n",min(r[i],query(i)));
return 0;
}