优秀设计网站大全,企业管理系统排名,wordpress文章页面添加字段,免费域名注册网简要题意 给出一个长度为n的字符串s[1]#xff0c;由小写字母组成。定义一个字符串序列s[1....k],满足性质#xff1a;s[i]在s[i-1] (i2)中出现至少两次#xff08;位置可重叠#xff09;#xff0c;问最大的k是多少#xff0c;使得从s[1]开始到s[k]都满足这样一个性…简要题意 给出一个长度为n的字符串s[1]由小写字母组成。定义一个字符串序列s[1....k],满足性质s[i]在s[i-1] (i2)中出现至少两次位置可重叠问最大的k是多少使得从s[1]开始到s[k]都满足这样一个性质。 \(n\le 200000\) Sol 一道适合练习SAM的right集合神题 神仙结论题 结论1 每次只算\(s[i-1]\)是\(s[i]\)的后缀的情况显然是不会影响答案的。 因为如果\(s[i-1]\)不是\(s[i]\)的后缀那么我们把不与\(s[i-1]\)匹配的那后面一截都去掉\(s[i]\)就会变短。 如果没变短之前它在某一个字符串里出现过了那么变短后显然还是出现过的。 这个结论是显然的也比结论2容易理解。 建立后缀自动机。 容易想到直接在parent树上自上向下DP 考虑如何判断x的祖先y所代表的子串是否在x中出现了两次\(len[x]\)表示\(x\)代表的最长子串长度假设\(x\)的\(right\)集合中存在一个位置\(p\) 那么\(p\)显然已经在\(y\)的\(right\)集合中了 我们只要判断\(y\)的\(right\)集合中有没有一个元素 在区间\([pos(x)-len(x)len(y),pos(x)-1]\)中判断y串是否出现两次即可。 这个容易线段树合并完成。 可以发现我们以上的做法都只考虑父亲代表的最长串都必须出现在x代表的最长串中。 这样有没有问题呢又如何dp呢 结论2 设s是某个节点u表示的最长串,v是u的祖先即串的后缀 则v表示的所有字符串在s上的匹配情况是等价的即不会出现有的能匹配、有的不能。 证明的话我们举个例子 \((1)\ \ \ \ \ \ abcb\) \((2)\ \ \ \ babcb\) \((s)\ \ \ \ \ \ abcbabcb\) 考虑反证 假设这里(s)的后缀(1)(2)均为v节点表示的串1成功匹配而2不行。 因为(2)所有显然还存在着这个串 \((3)\ \ \ \ babcbabcb\) 又因为(s)表示的已经是u的最长串了所以(3)串一定来自另一个节点。 设(3)串来自另一个节点wu是w的祖先。 根据定义知\[ |Right(u)| |Right(w)| \] 这样则一定存在一个位置p\[p ∈Right(u) - Right(w)\] 在这个位置只出现了(s)串而没有(3)串。 这样就存在一个位置使得只出现(1)串而没有(2)串。 这样得到(1)(2)两串\(Right\)集合不同 这与它们来自同一个节点矛盾 证毕. 有了结论2我们就可以设计dp状态了 \(dp[i]\)表示使用节点i最长的那个字符串的答案 转移的时候可以直接使用祖先节点j最长的那个字符串转移因为都等价啊 这样一来整个dp过程都是忽略那部分短串的就非常自然了。 这个dp显然可以倍增容易做到线性对深度Two-pointer。 #includeset
#includemap
#includecmath
#includevector
#includecstdio
#includecstring
#includecstdlib
#includealgorithm
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint,int pi;const int N400005;char S[N];
int n,tot(1),la,ch[N][26],len[N],fa[N],pos[N],rt[N],cnt,rk[N],ar[N],dp[N],fr[N],Ans;struct node {int lc,rc;
}t[N*20];void Upd(int u,int l,int r,int p)
{if(!u)ucnt;if(l!r){int m(lr)1;if(mp) Upd(t[u].lc,l,m,p);else Upd(t[u].rc,m1,r,p);}
}int Merge(int x,int y,int l,int r)
{if(!x||!y)return xy;int ocnt;if(l!r){int m(lr)1;t[o].lcMerge(t[x].lc,t[y].lc,l,m);t[o].rcMerge(t[x].rc,t[y].rc,m1,r);}return o;
}int Query(int u,int l,int r,int L,int R)
{if(!u||lR||rL)return 0;if(lLrR)return 1;int m(lr)1;return Query(t[u].lc,l,m,L,R)||Query(t[u].rc,m1,r,L,R);
}void extend(int id,int where)
{int pla;int nptot;len[np]len[p]1;pos[np]where;while(p !ch[p][id]){ch[p][id]np;pfa[p];}if(!p){fa[np]1;}else{int qch[p][id];if(len[p]1len[q]){fa[np]q;}else{int nqtot;len[nq]len[p]1;fa[nq]fa[q];pos[nq]pos[q];for(int i0; i26; i)ch[nq][i]ch[q][i];fa[np]fa[q]nq;while(p ch[p][id]q){ch[p][id]nq;pfa[p];}}}lanp;Upd(rt[la],1,n,where);
}void Sort()
{for(int i1; itot; i) ar[len[i]];for(int i1; in; i) ar[i]ar[i-1];for(int i1; itot; i) rk[ar[len[i]]--]i;
}int main()
{scanf(%d%s,n,S1);la1;for(int i1; in; i) extend(S[i]-a,i);Sort();for(int itot; i!1; i--){int urk[i],vfa[u];rt[v]Merge(rt[v],rt[u],1,n);}for(int i2; itot; i){int urk[i],vfa[u];if(v1){dp[u]1;fr[u]u;}else if(Query(rt[fr[v]],1,n,pos[u]-len[u]len[fr[v]],pos[u]-1)){dp[u]dp[v]1;fr[u]u;}else{dp[u]dp[v];fr[u]fr[v];}Ansmax(Ans,dp[u]);}printf(%d,Ans);return 0;
} 转载于:https://www.cnblogs.com/bestwyj/p/10847198.html
