网上有哪些网站做兼职,设计师拥有的设计导航,网站设计名称,响应式布局模板网站免费下载传送门
题意#xff1a;给定字符串SSS#xff0c;求一堆字符串s1,s2,s3,...,sks_1,s_2,s_3,...,s_ks1,s2,s3,...,sk#xff0c;满足s1s_1s1是SSS的子串#xff0c;且sis_isi在si−1s_{i-1}si−1中至少出现两次#xff0c;最大化kkk ∣S∣≤200000|S| \leq …传送门
题意给定字符串SSS求一堆字符串s1,s2,s3,...,sks_1,s_2,s_3,...,s_ks1,s2,s3,...,sk满足s1s_1s1是SSS的子串且sis_isi在si−1s_{i-1}si−1中至少出现两次最大化kkk
∣S∣≤200000|S| \leq 200000∣S∣≤200000
神仙题
显然建出后缀自动机然后在failfailfail树上乱搞
但很快发现不好描述出现两次
于是考虑回归到后缀自动机的本质endposendposendpos
对于子串S,TS,TS,T如果SSS在TTT中出现两次
那么在某一个TTT的覆盖范围里SSS出现了两次
换句话说对于TTT的任意一个endposendposendpos,记为pos[T]pos[T]pos[T],其覆盖范围为[pos[T]−len[T],pos[T]][pos[T]-len[T],pos[T]][pos[T]−len[T],pos[T]]
这段里出现了两个[pos[S]−len[S],pos[S]][pos[S]-len[S],pos[S]][pos[S]−len[S],pos[S]]
即[pos[T]−len[T]len[S],pos[T]][pos[T]-len[T]len[S],pos[T]][pos[T]−len[T]len[S],pos[T]]中有至少两个SSS的endposendposendpos
于是可以用可持久化线段树来维护由于某个点的endposendposendpos等于其failfailfail树的儿子的endposendposendpos的并集写个线段树合并即可。
查询的时候由于是单调的用倍增查最下面的满足条件的祖先。
复杂度O(nlog2n)O(nlog^2n)O(nlog2n)
#include iostream
#include cstdio
#include cstring
#include cctype
#define MAXN 400005
using namespace std;
namespace SGT
{int ch[MAXN5][2],sum[MAXN5],cnt;inline int copy(const int x){int anscnt;ch[ans][0]ch[x][0],ch[ans][1]ch[x][1],sum[ans]sum[x];return ans;}void insert(int x,int l,int r,int k){sum[xcnt];if (lr) return;int mid(lr)1;if (kmid) insert(ch[x][0],l,mid,k);else insert(ch[x][1],mid1,r,k);}int merge(int x,int y){if (!x||!y) return x|y;int pcopy(x);sum[p]sum[y];ch[p][0]merge(ch[p][0],ch[y][0]);ch[p][1]merge(ch[p][1],ch[y][1]);return p;}int getpos(int x,int l,int r){if (lr) return l;int mid(lr)1;if (sum[ch[x][0]]) return getpos(ch[x][0],l,mid);else return getpos(ch[x][1],mid1,r);}int query(int x,int l,int r,int ql,int qr){if (qllrqr) return sum[x];if (rql||qrl) return 0;int mid(lr)1;return query(ch[x][0],l,mid,ql,qr)query(ch[x][1],mid1,r,ql,qr);}
}
int n;
char s[MAXN];
namespace SAM
{int ch[MAXN][26],fa[MAXN],len[MAXN],pos[MAXN],tot1,las1;int rt[MAXN];void insert(int c){int curtot,plas;len[cur]len[p]1;lascur;for (;p!ch[p][c];pfa[p]) ch[p][c]cur;if (!p) return (void)(fa[cur]1);int qch[p][c];if (len[q]len[p]1) fa[cur]q;else{int _qtot;len[_q]len[p]1;fa[_q]fa[q];fa[q]fa[cur]_q;memcpy(ch[_q],ch[q],sizeof(ch[q]));for(;ch[p][c]q;pfa[p]) ch[p][c]_q;}}int jump[MAXN][20];int a[MAXN],c[MAXN],f[MAXN]{-1};inline bool check(int x,int y){return len[x]0||SGT::query(rt[x],1,n,pos[y]-len[y]len[x],pos[y])2;}int build(){for (int i1;in;i) insert(s[i]-a),SGT::insert(rt[las],1,n,i);for (int i1;itot;i) c[len[i]];for (int i1;in;i) c[i]c[i-1];for (int itot;i1;i--) a[c[len[i]]--]i;for (int itot;i1;i--){pos[a[i]]SGT::getpos(rt[a[i]],1,n);rt[fa[a[i]]]SGT::merge(rt[fa[a[i]]],rt[a[i]]);}for (int i1;itot;i){jump[a[i]][0]fa[a[i]];for (int k1;k20;k) jump[a[i]][k]jump[jump[a[i]][k-1]][k-1];int anca[i];for (int k19;k0;k--) if (!check(jump[anc][k],a[i])) ancjump[anc][k];ancfa[anc];f[a[i]]f[anc]1;}int mx0;for (int i1;itot;i) mxmax(mx,f[i]);return mx;}
}
int main()
{scanf(%d,n);scanf(%s,s1);printf(%d\n,SAM::build());return 0;
}
