字符串选讲

2019-08-10 总结字符串 0 评论

字符串选讲

只会讲几个简单模版，~~觉得简单的可以跑路了~~整理一下概念，难度随机排列

有几个概念一直绕来绕去的：

区间/全局+位置不同/本质不同+子/回文+序列/串

1. 全局+位置不同+子串

不会的可以丢出去了...

2.全局+本质不同+子串

同上

3. 全局+位置不同+子序列

同上

4.全局+位置不同+回文串

manacher

什么你不会manacher?

5.全局+本质不同+子序列

序列自动机+记忆化搜索+高精度

什么你不会序列自动机？

就是个~~二维数组~~好吧

~~该怎么构造怎么构造~~¹

int trans[N][26],nxt[26];

for(int i=n;i;i--){
    memcpy(trans[i],nxt,sizeof nxt);
    nxt[s[i]-'a']=i;
}
memcpy(trans[0],nxt,sizeof nxt);

6.全局+位置不同+回文序列

表示我只会DP $$ $$

~~欢迎暴打讲课人~~

7. 全局+本质不同+回文串

听说有manacher+后缀数组做法，然而不是很懂那些人在写什么~~会的人可以上来讲~~

我今天只是来讲板子的，于是：

回文自动机即可。²

回文自动机上一个节点代表一个本质不同的回文串，总节点个数个根节点就是本质不同的回文串个数，这样讲能听懂了吧=.=

什么你不会回文自动机？

8. 全局+本质不同+回文序列

完全不会搞=.=, dfs吗？只是凑数的 ~~欢迎暴打讲课人X2~~

9. 区间+位置不同+子串

：妹神，这题咋做啊。

：我不会

：你题都没看你就说不会，你咋这么假

：不是，我是真不会

：哦，那好嘛，让你看几秒，现在会了吗

：还是不会

：？？？这妹神怎么走水，丢出去丢出去³

10.区间+位置不同+子序列

：该怎么怎么

：不是，这题你还要？

：哦，我傻了

：哎哟~~~假死了⁴

11. 区间+位置不同+回文串

这好像是道原题但不是所有人都改了（记不到题号了，欢迎某神妹说一下）

蜜汁画外音：预处理出串的manacher数组，然后你瞎搞一下就完了。⁵

？？？

=.=

设manacher预处理出来的每个位置最多往左右延伸的距离数组为f

相当于求

解不等式所以取可得对于左边限制更强区间位置不同回文串个数然后继续解然后就是查满足且的的之和以及之和以及个数，没被“挡住”的的个数直接用去减，右边是相似的，然后就随便写完了

可以用树状数组优化常数，也可以用主席树在线

12. 区间+本质不同+子串

课件里提到过~~（当时在冬眠？完全没印象了）~~

先离线询问，然后变成右端点r每次往右拓展。怎么算答案？使用线段树记录对于每个左端点l有多少个子串最后一次出现是从l开始的，答案即l-r的区间和。

怎么维护？考虑拓展之后以当前r结尾的串一定在后缀树上是一条到根的链。之前这条链上有一些点，这些点的最后一次出现位置（的右端点）将要变为r，即用LCT维护，每个节点记一下所属的right集合最大值，然后新加一个点就是对于一条链的right集合最大值全部赋值为r，即access操作。

(例如从右往左加入到时)

(图来自冬令营课件，因为懒得画了)

加入前：

加入后：

然后可以知道在这棵LCT中所有在同一棵splay上的节点的right集合最大值都是相等的（归纳法）

每次右端点右移时直接区间都加上，表示左端点在右端点在的子串出现次数都加上，但是有可能以结尾的某些子串在之前出现过，那么它们在右端点移到之前的最后一次出现的左端点的值则要减去，（这些子串最后一次出现位置改变了）这可以在access途中维护。

即把一些左端点在右端点在的点的贡献删掉，再把其右端点改为当前的 ~~代码应该好懂~~

（注意mnlen的含义）

//hackerrank how many substrings
//or hdu4622(Weakened version)
inline void pushup(int x){mnlen[x]=min(mnlen[lx],min(len[sam::fa[x]]+1,mnlen[rx]));}

inline void pushdown(int x){
  rig[lx]=max(rig[lx],rig[x]);
  rig[rx]=max(rig[rx],rig[x]);
}

inline void access(int x,int n){
  for(int y=0;x;x=fa[y=x]){
    splay(x);
    pushdown(x);
    if(len[x]&&rig[x])
      mdy(rig[x]-len[x]+1,rig[x]-mnlen[x]+1,-1);
    rx=y;
    pushup(x);
    if(!fa[x])rig[x]=n;
  }
}

13.区间+本质不同+子序列

好像又是原题，不过原题字符集大小只有，改成也差不多吧

好像讲过了，那我就~~不讲了~~再讲一遍

设dp[i][j]表示从左到右到第i位，以字符j结尾的子序列个数

于是

$$ $$ 转移看成矩阵可得：(假设字符集大小为3)

(矩阵公式太难打以下矩阵全部识别自原题解)

然后肉眼观察手推⁶可得出转移矩阵的逆矩阵然后答案即为然后预处理前缀积可做到

然后可以通过非零项只有项来做到~~我不会~~

讲下最优解

考虑矩阵左乘另一个矩阵的含义

即

对于 $这一项$

否则这是什么意思？相当于矩阵的第s[这一项]列的每一个数都变成所在行的行和了，其余不变

这个是可以通过维护每一行行和维护的

对于右乘一个矩阵是相当于每行的除了第s[这一项]列的这个数都减等于这个数~~（这真可以手推）~~，维护一下每一行所有数一共减了多少即可

再来看我们求什么，一个全是的行向量右乘相当于只有行，预处理出来列和，然后一个只有最后一项的列向量左乘只有列，预处理出行和，然后即可（即 )复杂度是的

//可能预处理的是A^-1左乘，A右乘，不过等价的
//B即是A^-1
for(int i=0;i<M;i++)A[i][i]=B[i][i]=sum_A[i]=1;
preB[0][M-1]=1;
for(int i=1;i<=n;i++){
	int v=s[i]-'a';
	for(int j=0;j<M;j++){
		dec(sum_A[j],A[v][j]);
		inc(A[v][j],sum_A[j]);
		inc(sum_A[j],A[v][j]);
		inc(B[j][v],sum_B[j]);
		dec(sum_B[j],B[j][v]);
		dec(B[j][v],sum_B[j]); 
		/*
		上面三行等价于
		int tmp=sum_B[j];
		sum_B[j]=sub(0,B[j][v]);
		B[j][v]=add(mul(2,B[j][v]),tmp);
		*/
	}
	
	for(int j=0;j<M;j++){
		preA[i][j]=sum_A[j];
		preB[i][j]=add(B[j][M-1],sum_B[j]);
	}
}

//算答案
for(int i=0;i<M;i++)inc(ans,mul(preB[l-1][i],preA[r][i]));

14.区间+本质不同+回文串

有一个性质就是一个回文串的所有回文后缀可以分为不超过个等差数列（证明可以翻鏼课件）

还是和求区间本质不同子串相似的做法，先离线，考虑右端点每次右移，不同的是直接维护左端点在每个位置时的答案。

考虑怎么求以新增的r结尾的串的贡献

大概这个样子，会造成若干个回文串最后一次出现位置被更新，例如红色回文串就会以红色串上次出现左端点到这次红色串出现的左端点为左端点的区间内的本质不同回文串个数加一，绿色的同理，但可以注意到它们可以恰好拼成一个区间，那么就可以一起修改了。

=.=不对吧，如果绿色除了r结尾最后一次出现不以红色开头呢？不会算成（如下绿色框）吗？

比如这样

=v=你冷静观察下就会发现红色串在回文树上的父亲不是绿色串而是蓝色串，根据回文树的定义蓝色串一定是最长的，绿色的出现位置会形成一个等差数列，~~（意会一下可以知道）~~形成的回文串出现位置一定是连着的，所以还是没有问题的

//bzoj5384
inline void append(int n){
    int p=lst,c=s[n]-'a';
    while(s[n-len[p]-1]^s[n])p=fa[p];
    if(!ch[p][c]){
        int q=fa[p];
        while(s[n-len[q]-1]^s[n])q=fa[q];
        len[++ptr]=len[p]+2;
        fa[ptr]=ch[q][c];
        ch[p][c]=ptr;
        dif[ptr]=len[ptr]-len[fa[ptr]];
        anc[ptr]=dif[ptr]^dif[fa[ptr]]?fa[ptr]:anc[fa[ptr]];
    }
    lst=ch[p][c];
}

for(int i=1;i<=n;i++){
        for(int u=pos[i];u;u=anc[u]){
            int l=max(1,qry(id[u],id[u]+sz[u]-1)-len[u]+2);
            int r=i-(len[anc[u]]+len[u]-len[fa[u]])+1;
            bit.add(l,r);
        }
        mdy(id[pos[i]],i);
        while(!q[i].empty()){
            pii x=q[i].back();q[i].pop_back();
            ans[x.first]=bit.qry(x.second);
        }
    }

15 区间+位置不同+回文序列

同，只会 >_<

16.区间+本质不同+回文序列

完全不会=.=

：Ber！这不XX题吗，就XXOJXXXX和XXOIXXXX的那道一样的

（其他做过该题的与没做过该题的）：？？？

：哦，那还是差不多嘛，你看都是XX再套个XX就完了

：？？？所以就一样？？？⁷

再讲几个板子~~来拖时间~~吧 ~~（毕竟除了板子就啥都不会了）~~

真一点的广义后缀自动机

可能插入一个新节点时已经有从之前到现在的转移边了，判断一下len，可能需要拆之前的点（其实和之前拆点的写法几乎一样）

inline void append(int c){
  int p=lst;
  if(ch[p][c]){
    if(len[ch[p][c]]==len[p]+1)lst=ch[p][c];
    else{
      int q=ch[p][c],nq=++ptr;
      len[nq]=len[p]+1;
      fa[nq]=fa[q];
      fa[q]=nq;
      memcpy(ch[nq],ch[q],sizeof ch[q]);
      for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
      lst=nq;
    }
  }else{
      //printf("p=%d c=%d\n",p,c);
    int x=++ptr;len[x]=len[p]+1;lst=x;
    while(p&&!ch[p][c])ch[p][c]=x,p=fa[p];
    if(!p)fa[x]=1;
    else{
      int q=ch[p][c];
      if(len[q]==len[p]+1)fa[x]=q;
      else{
        int nq=++ptr;
        len[nq]=len[p]+1;
        fa[nq]=fa[q];
        fa[x]=fa[q]=nq;
        memcpy(ch[nq],ch[q],sizeof ch[q]);
        for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
      }
    }
  }
}

双端插入的回文自动机

记一下两端加入的回文串的最后插入位置（及总串的最长回文前缀和最长回文后缀），然后和普通回文自动机一样的写就行了，注意一点就是根据定义当插入后当前节点长度变为总长的时候要把另一端的最后插入位置也变成当前节点。=.=看代码吧

//hdu5421
//f=1 left 
//f=2 right
inline void append(int n,int f){
    int p=lst[f-1],c=s[n]-'a',ff=f*2-3;//f=1 -> ff=-1 | f=2 -> ff=1
    while(s[n-len[p]*ff-ff]^s[n]) p=fa[p];
    if(!ch[p][c]){
        int q=fa[p];
        while(s[n-len[q]*ff-ff]^s[n])q=fa[q];
        len[++ptr]=len[p]+2;
        fa[ptr]=ch[q][c];
        lst[f-1]=ch[p][c]=ptr;
        if(r-l+1==len[ptr])lst[!(f-1)]=ptr;//!
        dep[ptr]=dep[fa[ptr]]+1;
    }else lst[f-1]=ch[p][c];
    sum+=dep[ch[p][c]];
}

后缀平衡树

维护一个母串，支持加后缀、删后缀、询问一个模版串出现次数。

母串模版串都反过来，变为每次在左边加减字符就可以动态的维护后缀数组。

新加入节点时最好能比较rk ，于是使用平衡树维护一个long long数组val

类似于最好使用重量平衡树 或替罪羊

查串出现次数即查，可在平衡树上查找（这里判断字符串大小听说不知道为什么二分没有暴力for快 ~~我不知道我瞎说的我自己这题也没过被卡常了~~）

//bzoj4768
inline void relabel(int x=X,ll l=L,ll r=R){
  if(!x)return;
  val[x]=mid;
  relabel(ch[x][0],l,mid);
  relabel(ch[x][1],mid,r);
  if(x==X)X=0;
}

inline void ins(int pos,int &x=rt,ll l=0,ll r=1e18){
  if(!x){
    x=newnode(pos,mid);
    return;
  }
  int t=s[x]<s[pos]||(s[x]==s[pos]&&val[x-1]<val[pos-1]);
  ins(pos,ch[x][t],t?mid:l,t?r:mid);
  if(rnd[ch[x][t]]<rnd[x]){
    rot(x,t);
    X=x;L=l;R=r;
  }
  pushup(x);
}

inline bool les(int x){
  for(int i=0;i<min(len,x);i++)if(s[x-i]^str[i])
    return s[x-i]<str[i];
  return x<len;
}

inline void qry(int x=rt){
  while(x){
    if(les(x))ans+=sz[ch[x][0]]+1,x=ch[x][1];
    else x=ch[x][0];
  }
}

switch(type[0]){
  case 'Q':{
             scanf("%s",str);
             len=strlen(str);
             decode(mask);
             reverse(str,str+len);
             ans=0;
             qry();
             ans=-ans;
             str[len++]='Z'+1;
             qry();
             printf("%d\n",ans);
             mask^=ans;
             break;
           }
  case 'A':{
             scanf("%s",str);
             len=strlen(str);
             decode(mask);
             for(int i=0;i<len;i++)s[++n]=str[i],ins(n),relabel();
             break;
           }
  case 'D':{
             int x;
             scanf("%d",&x);
             while(x--){
               del(n);
               s[n--]=0;
             }
             break;
           }
}

拓展KMP

国外好像叫Z-algorithm，用来计算串每一个后缀和串的

设答案数组为ext[i]即S[i]与T的再预处理出一个nxt[i]表示S[i]与S[0]的长度

：就，你记录一个最长延伸到的点，再用类似manacher的方法算就完了。⁸

？？？

就分三种情况讨论 EXKMP

这种情况我们什么也不知道，只能令

EXKMP2

这表示

什么意思呢？即

第位与的已经在第项算过了，且肯定不会变多，可以直接赋值为

EXKMP3

这时最上方两个蓝色的串处于红色串没包含的部分一定不相等（否则红色串将更长），只能赋值为已知的长度即

可以把并为一种

~~（代码巨短无比）~~

（这是预处理至于计算就基本完全一样了）

//luogu P5410 
int mid=0;
for(int i=1;i<n;i++){
  if(nxt[mid]+mid>=i+nxt[i-mid])nxt[i]=nxt[i-mid];
    else nxt[i]=max(0,mid+nxt[mid]-i);
  while(i+nxt[i]<=n&&s[nxt[i]]==s[i+nxt[i]])nxt[i]++;
  if(i+nxt[i]>mid+nxt[mid])mid=i;
}

mid=0;
while(t[ext[0]]==s[ext[0]])ext[0]++;
for(int i=1;i<m;i++){
  if(ext[mid]+mid>=i+nxt[i-mid])ext[i]=nxt[i-mid];
    else ext[i]=max(0,mid+ext[mid]-i);
  while(i+ext[i]<=m&&s[ext[i]]==t[i+ext[i]])ext[i]++;
  if(i+ext[i]>mid+ext[mid])mid=i;
}

Lyndon分解

定义：对于字符串，若的最小后缀为其本身，那么称为串

性质：任意字符串都可以分解为，其中为串且。且这种分解方法是唯一的

证明：到处都有就不搬了。。。~~我证明不过关~~⁹

如何构造：考虑维护当前结尾的若干个相等的串，每次往右移，令未确定分解的开始位置为，当前新增位置为 , 是这一位在之前循环的对应位置，分情况讨论 $周期不变形成了一个更大的串一定不能与左边的合并了，所以记录答案再从所在的循环头部开始$

大概是这样

//loj129
for(int i=1;i<=n;){
  int j=i,k=i+1;
  for(;k<=n&&s[j]<=s[k];k++){
    if(s[k]==s[j])j++;
    else j=i;
  }
  while(i<=j){
    i+=k-j;
    printf("%d ",i-1);
  }
}

如果有时间，再讲点奇奇怪怪的题 ~~真 · 只讲板子.jpg~~

CF666E

Description

给你一个串以及一个字符串数组，次询问，每次问的子串在中的哪个串里的出现次数最多，并输出出现次数。如有多解输出最靠前的那一个。

Sample Input
1
2
3
4
5
6
7
8
suffixtree
3
suffixtreesareawesome
cartesiantreeisworsethansegmenttree
nyeeheeheee
2
1 2 1 10
1 3 9 10
Sample Output
1
2
1 1
3 4
Constraint

Solution

建出广义每个节点使用线段树合并维护每个节点在每个中出现次数

对每个前缀记录匹配到广义的哪个节点以及匹配长度，查询时如果不足直接返回，否则倍增到找到最长的长度大于等于的的后缀树上的祖先，在该祖先的线段树里随便查询一下就行了

（注意线段树合并的时候要新建节点，不然信息（很有可能）被破坏，~~小样例还测不出来~~）

Code

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define FIO "cf666e"
using namespace std;
 
const int N=5e5+5,M=5e4+5,C=26,lgM=18;
 
int n,ptr=1,m;
char s[N],t[M];
 
int rt[M<<1];
namespace seg{
  int ptr;
  int ch[M*80][2];
  pii tr[M*80];
#define lk ch[k][0]
#define rk ch[k][1]
#define mid (l+r>>1)
  inline void mdy(int &k,int pos,int l=1,int r=m){
    if(!k)k=++ptr;
    if(l==r){
      tr[k]=pii(tr[k].second+1,-l);
      return;
    }
    if(pos<=mid)mdy(lk,pos,l,mid);
    else mdy(rk,pos,mid+1,r);
    tr[k]=max(tr[lk],tr[rk]);
  }
  inline pii qry(int k,int ql,int qr,int l=1,int r=m){
    if(!k)return pii(0,-ql);
    if(ql<=l&&r<=qr)return tr[k];
    if(qr<=mid)return qry(lk,ql,qr,l,mid);
    if(mid<ql)return qry(rk,ql,qr,mid+1,r);
    return max(qry(lk,ql,mid,l,mid),qry(rk,mid+1,qr,mid+1,r));
  }
 
inline int merge(int x,int y,int l=1,int r=m){
  if(!x||!y)return x|y;
  int z=++ptr;
  if(l==r){
    tr[z]=pii(tr[x].first+tr[y].first,-l);
    return z;
  }
  ch[z][0]=merge(ch[x][0],ch[y][0],l,mid);
  ch[z][1]=merge(ch[x][1],ch[y][1],mid+1,r);
  tr[z]=max(tr[ch[z][0]],tr[ch[z][1]]);
  return z;
}
 
#undef lk
#undef rk
#undef mid
}
 
 
int fa[M<<1],ch[M<<1][C],len[M<<1],lst;
inline void append(int c,int id){
  int p=lst;
  if(ch[p][c]){
    if(len[ch[p][c]]==len[p]+1)lst=ch[p][c];
    else{
      int q=ch[p][c],nq=++ptr;
      len[nq]=len[p]+1;
      fa[nq]=fa[q];
      fa[q]=nq;
      memcpy(ch[nq],ch[q],sizeof ch[q]);
      for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
      lst=nq;
    }
  }else{
      //printf("p=%d c=%d\n",p,c);
    int x=++ptr;len[x]=len[p]+1;lst=x;
    while(p&&!ch[p][c])ch[p][c]=x,p=fa[p];
    if(!p)fa[x]=1;
    else{
      int q=ch[p][c];
      if(len[q]==len[p]+1)fa[x]=q;
      else{
        int nq=++ptr;
        len[nq]=len[p]+1;
        fa[nq]=fa[q];
        fa[x]=fa[q]=nq;
        memcpy(ch[nq],ch[q],sizeof ch[q]);
        for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
 
      }
    }
  }
  seg::mdy(rt[lst],id);
}
 
int h[M<<1],nxt[M<<1],to[M<<1],ecnt;
inline void add(int u,int v){nxt[++ecnt]=h[u];h[u]=ecnt;to[ecnt]=v;}
 
int anc[M<<1][lgM];
inline void dfs(int u=1){
  for(int i=1;anc[u][i-1];i++)anc[u][i]=anc[anc[u][i-1]][i-1];
  for(int i=h[u],v;i;i=nxt[i])anc[v=to[i]][0]=u,dfs(v),rt[u]=seg::merge(rt[u],rt[v]);
}
 
int q,pos[N],L[N];
int main(){
  scanf("%s",s+1);
  n=strlen(s+1);
  scanf("%d",&m);
  for(int i=1;i<=m;i++){
    scanf("%s",t+1);
    int len=strlen(t+1);
    lst=1;
    for(int j=1;j<=len;j++)append(t[j]-'a',i);
  }
  for(int i=2;i<=ptr;i++)add(fa[i],i);
  dfs();
  
  for(int i=1,p=1,l=0;i<=n;i++){
    int c=s[i]-'a';
    while(p&&!ch[p][c])p=fa[p],l=len[p];
    if(!p){
      p=1;l=0;
    }else{
      p=ch[p][c];
      l++;
    }
    pos[i]=p;L[i]=l;
  }
  scanf("%d",&q);
  while(q--){
    int l,r,ql,qr;
    scanf("%d%d%d%d",&ql,&qr,&l,&r);
    l=r-l+1;
    if(L[r]<l){printf("%d %d\n",ql,0);continue;}
    int u=pos[r];
    for(int i=lgM-1;~i;i--)if(len[anc[u][i]]>=l)u=anc[u][i];
    pii ans=seg::qry(rt[u],ql,qr);
    printf("%d %d\n",-ans.second,ans.first);
  }
  return 0;
}

LuoguP4482

Description

求区间最长长度

: 对于给定的串，最大的使得 , 为的长度。

Sample Input
1
2
3
4
5
abbabbaa
3
1 8
1 7
2 7
Sample Output
1
2
3
1
4
3
Constraint

Solution

题意可以转化为对于一个找到一个最大的满足使得，在后缀树上即是r所代表的节点的某个祖先x的right集合内大于等于l且满足的最大的

一个在串随机的情况下的可能的算法就是每次从 r 的节点暴力往上跳使用线段树合并/Set启发式合并找到符合要求的right集合内的值，期望情况下SAM大概树高是log的，大概可以过这部分分

考虑正解链分治，之前的做法复杂度不对的原因是每个询问可能被处理树高次，在树高特别高（如全是一个字符）时会挂掉。

那么能否离线下来呢？如果只是保留下来对每个点的询问还是会查若干遍，因为要查的和len[x]和l都有关，转化式子可以对每个节点以i为下标维护i-len[x]的最小值即求一段区间最靠右的满足的位置，然后链剖，发现我们每次询问的是若干重链的前缀的信息，把询问到根的路径拆成若干条重链前缀的询问，对每个点先继承重链父亲（如果有）的状态，再加入自己的虚子树（直接暴力DFS，因为一个点最多往上走log跳虚边即最多在log个点的虚子树内），计算在这个节点的询问，再递归处理子树，然后计算答案在自己子树内时的影响（即和之前一样维护right集合，用个rig[u].lower_bound(min(ql[cur]+len[u],qr[cur]))）

如这样，从询问点到根的路径被分为条重链的前缀。

以的点和所求在最上面红点到根的前缀时对答案的影响：

首先会继承继承到根的重链的虚子树部分（蓝色三角）的信息if(u^top[u])rt[u]=rt[fa[u]];

然后对于每一个询问直接seg::qry(rt[u],qr[cur]-1,ql[cur]-1)即可

然后是恰为当前点的答案，加入所有虚子树（绿色三角）内right-len[x] （这时right集合还没有合并，最多有一个值）

inline void dfs4(int u,int x){
  if(rig[u].size())seg::mdy(rt[x],*rig[u].begin(),*rig[u].begin()-len[x]);
  for(int i=h[u],v;i;i=nxt[i])dfs4(v=to[i],x);
}

 for(int i=h[u],v;i;i=nxt[i])if((v=to[i])^son[u])dfs4(v,u);

递归计算所有儿子的信息，然后合并这个点的right集合，更新答案在这个子树内的影响

Code

#include<bits/stdc++.h>
#define ll long long
#define FIO "P4482"
using namespace std;

const int N=2e5+5,C=26,INF=1e9;

inline void chkmax(int &a,const int &b){if(a<b)a=b;}
inline void chkmin(int &a,const int &b){if(a>b)a=b;}

int n,m,fa[N<<1],len[N<<1];
char s[N];

set<int>rig[N<<1];

int R[N<<1];

namespace sam{
  int lst=1,ptr=1,ch[N<<1][C];

  inline void append(int n){
    int c=s[n]-'a',p=lst,x=++ptr;len[x]=len[p]+1;lst=x;rig[x].insert(n);R[x]=n;
    for(;p&&!ch[p][c];p=fa[p])ch[p][c]=x;
    if(!p)fa[x]=1;
    else{
      int q=ch[p][c];
      if(len[q]==len[p]+1)fa[x]=q;else{
        int nq=++ptr;
        len[nq]=len[p]+1;
        fa[nq]=fa[q];
        fa[q]=fa[x]=nq;
        memcpy(ch[nq],ch[q],sizeof ch[q]);
        for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
      }
    }
  }

}

int h[N<<1],nxt[N<<1],to[N<<1],ecnt;
inline void add(int u,int v){nxt[++ecnt]=h[u];h[u]=ecnt;to[ecnt]=v;}

int sz[N<<1],top[N<<1],son[N<<1];
inline void dfs1(int u=1){
  sz[u]=1;
  for(int i=h[u],v;i;i=nxt[i]){
    dfs1(v=to[i]),sz[u]+=sz[v];
    if(!son[u]||sz[v]>sz[son[u]])son[u]=v;
  }
}

inline void dfs2(int u=1,int tp=1){
  top[u]=tp;
  if(son[u])dfs2(son[u],tp);
  for(int i=h[u],v;i;i=nxt[i])if((v=to[i])^son[u])dfs2(v,v);
}


int pos[N],rt[N<<1];

int ql[N],qr[N],ans[N];
namespace seg{
  int mn[N*50],ptr,ch[N*50][2];

#define lk ch[k][0]
#define rk ch[k][1]
#define mid (l+r>>1)

  inline int qry(int k,int qr,int val,int l=1,int r=n){
    if(mn[k]>val)return -INF;
    if(l==r)return l;
    if(r<=qr){
      if(mn[rk]<=val)return qry(rk,qr,val,mid+1,r);
      return qry(lk,qr,val,l,mid);
    }else{
      if(qr<=mid)return qry(lk,qr,val,l,mid);
      else return max(qry(lk,mid,val,l,mid),qry(rk,qr,val,mid+1,r));
    }
  }

  inline void mdy(int &k,int pos,int val,int l=1,int r=n){
    if(!k)k=++ptr;
    chkmin(mn[k],val);
    if(l==r)return;
    if(pos<=mid)mdy(lk,pos,val,l,mid);
    else mdy(rk,pos,val,mid+1,r);
  }
}

inline void dfs4(int u,int x){
  if(rig[u].size())seg::mdy(rt[x],*rig[u].begin(),*rig[u].begin()-len[x]);
  for(int i=h[u],v;i;i=nxt[i])dfs4(v=to[i],x);
}

vector<int>q[N<<1];

inline void merge(int u,int v){
  if(rig[u].size()<rig[v].size())swap(rig[u],rig[v]);
  for(set<int>::iterator it=rig[v].begin();it!=rig[v].end();it++)rig[u].insert(*it);
}

inline void dfs3(int u=1){
  if(u^top[u])rt[u]=rt[fa[u]];
  for(int i=0,sz=q[u].size();i<sz;i++)
    chkmax(ans[q[u][i]],seg::qry(rt[u],qr[q[u][i]]-1,ql[q[u][i]]-1));

  for(int i=h[u],v;i;i=nxt[i])if((v=to[i])^son[u])dfs4(v,u);
  assert(rig[u].empty()||*rig[u].begin()==R[u]);
  if(rig[u].size())seg::mdy(rt[u],*rig[u].begin(),*rig[u].begin()-len[u]);

  for(int i=h[u],v;i;i=nxt[i]){
    dfs3(v=to[i]);
    merge(u,v);
  }

  for(int i=0,sz=q[u].size();i<sz;i++){
    set<int>::iterator  it=rig[u].lower_bound(min(ql[q[u][i]]+len[u],qr[q[u][i]]));
    if(it!=rig[u].begin()) chkmax(ans[q[u][i]],*--it);
  }
}

int main(){
  memset(seg::mn,0x3f,sizeof seg::mn);
  scanf("%s%d",s+1,&m);
  n=strlen(s+1);
  for(int i=1;i<=n;i++)sam::append(i),pos[i]=sam::lst;
  for(int i=2;i<=sam::ptr;i++)add(fa[i],i);
  dfs1();dfs2();
  for(int i=1;i<=m;i++){
    scanf("%d%d",&ql[i],&qr[i]);
    ans[i]=ql[i]-1;
    for(int u=pos[qr[i]];u;u=fa[top[u]])
      q[u].push_back(i);
    
  }
  dfs3();

  for(int i=1;i<=m;i++)printf("%d\n",ans[i]-ql[i]+1);
  return 0;
}

JSOI2019节日庆典

Description

对于给定字符串的每一个前缀，求出。

定义为最小的满足

其中 (冒号表示字符串拼接)

Sample Input
1
abaacaba
Sample Output
1
1 1 3 3 3 6 3 8

Solution

可以尝试记录到当前点为止可能成为答案点的集合，这些起始点之间任意两个的都一定能够延伸到当前点（否则的话无论后面再加什么字符，有一位大了的一定永远大于另一个）

考虑有两个候选答案，，它们关系如下图

那么可以看出红色串一定是某个串重复若干遍最后截了一部分（可能没有）形成的，

假设此时 ,那么我们可以找到之后的第一个开始的位置记为 ,并把最后剩下的不满一个的记为，左边记为，之后出现了次

然后我们考虑原题中的函数然后考虑相邻两项大小关系的充要条件非常神奇的发现这两个条件居然等价！所以要么是要么是无论哪一种都不会是答案点，所以可以去掉，不过这一切都要建立在一个前提：

能找得到一个这样的，即

可以证明这样每两个相邻的候选点到最右端点的距离都至少乘所以总共只会有个候选点，暴力判断复杂度也才（好像这题有做法没看懂）

至于怎么判断候选点哪个最优，可以发现实际上就是求前缀和某一后缀的大小关系，用上面提到的拓展KMP算法求出每个位置与的即可

Code

#include<bits/stdc++.h>
#define ll long long
#define FIO "P5334"
using namespace std;

const int N=3e6+5;

int n,nxt[N];
char s[N];

inline int cmp(int x,int l){
  //printf("cmp %d %d=%d\n",x,l,nxt[x]<l?(s[nxt[x]]<s[x+nxt[x]]?-1:1):0);
    return nxt[x]<l?(s[nxt[x]]<s[x+nxt[x]]?-1:1):0;
}

int main(){
  scanf("%s",s);
  n=strlen(s);
  int mid=0;
  for(int i=1;i<n;i++){
    nxt[i]=mid+nxt[mid]>=i+nxt[i-mid]?nxt[i-mid]:max(0,mid+nxt[mid]-i);
    while(i+nxt[i]<n&&s[i+nxt[i]]==s[nxt[i]])nxt[i]++;
    if(i+nxt[i]>mid+nxt[mid])mid=i;
  }
  nxt[0]=n;

  vector<int>p,q;
  for(int i=0;i<n;i++){
    p.push_back(i);q.clear();
    for(int j=0,sz=p.size();j<sz;j++){
      while(!q.empty()&&s[i]<s[q.back()+i-p[j]])q.pop_back();
      if(q.empty()||(s[i]==s[q.back()+i-p[j]]&&(i-p[j]+1<<1)<i-q.back()+1))q.push_back(p[j]);
    }
    p=q;
    int ans=p[0];
    for(int j=0,sz=p.size();j<sz;j++){
      int x=p[j],opt=cmp(ans+i-x+1,x-ans);
      if(opt<0||(!opt&&cmp(x-ans,ans)>0))ans=x;
    }
    //printf("%d\n",ans+1);
    printf("%d%c",ans+1,i^n-1?' ':'\n');
  }
  return 0;
}

总结

居然水到词了...希望对大家有帮助。~~作图累死了，以后没事不写题解了~~ ~~（这种题解可能1篇比某神人5篇长了，要是每个人题解都这样图文并茂感觉做题会轻松很多)~~

参考资料

该怎么dp怎么dp就行了吧————《衍芃福音——雅礼集训》第10章——数列↩︎
贪心即可————《衍芃福音——雅礼集训》第1章——矩阵↩︎
《衍芃福音——讲座》第?章——走水↩︎
《衍芃福音——讲座》第?章——我傻了↩︎
《衍芃福音——机房训练》第?章——瞎搞↩︎
你手推嘛，我是手推的————《衍芃福音——机房评讲》第?章——讲题↩︎
《衍芃福音——机房训练》第?章——口胡↩︎
《衍芃福音——机房评讲》第?章——就完了↩︎
你DP不过关!————《衍芃福音——机房评讲》第?章——怒斥↩︎

本文链接： https://20021123.xyz/2019/08/10/字符串选讲/

版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

不知不觉Acmer & Student

Never Settle