轻淘客一键做网站,创新驱动发展战略意义,网站开发需要团队吗,网页游戏怎么在手机上玩P2463 [SDOI2008]Sandy的卡片 题意 给\(n(\le 1000)\)串#xff0c;定义两个串相等为“长度相同#xff0c;且一个串每个数加某个数与另一个串完全相同”#xff0c;求所有串的最长公共子串#xff0c;每个串长\(\le 101\)#xff0c;值域\(\in [0,1864]\) 先差分一下定义两个串相等为“长度相同且一个串每个数加某个数与另一个串完全相同”求所有串的最长公共子串每个串长\(\le 101\)值域\(\in [0,1864]\) 先差分一下然后连在一起中间加分隔符建sa 然后dp一下要用到lcp复杂度\(O(nm^2n\log n)\) Code: #include cstdio
#include algorithm
using std::min;
using std::max;
const int N2e5;
int tax[N],sa[N],Rank[N],sec[N],n,m2000,hei[N],st[N][18],Log[N];
int s[N],dp[N],L[110],R[110],num,mi[1100];
void Rsort()
{for(int i1;im;i) tax[i]0;for(int i1;in;i) tax[Rank[i]];for(int i1;im;i) tax[i]tax[i-1];for(int in;i;i--) sa[tax[Rank[sec[i]]]--]sec[i];
}
bool cmp(int x,int y,int l){return sec[x]sec[y]sec[xl]sec[yl];}
void SuffixSort()
{for(int i1;in;i) Rank[i]s[i],sec[i]i;Rsort();for(int w1,p0;pn;mp,w1){p0;for(int in-w1;in;i) sec[p]i;for(int i1;in;i) if(sa[i]w) sec[p]sa[i]-w;Rsort(),std::swap(Rank,sec),Rank[sa[1]]p1;for(int i2;in;i) Rank[sa[i]]cmp(sa[i],sa[i-1],w)?p:p;}//h[i]h[i-1]-1;for(int i1,p0,j;in;hei[Rank[i]]p,i)for(pp?p-1:p,jsa[Rank[i]-1];s[ip]s[jp];p);Log[0]-1;for(int i1;in;i) st[i][0]hei[i],Log[i]Log[i1]1;for(int j1;j17;j){for(int i1;in-(1j)1;i)st[i][j]min(st[i][j-1],st[i(1j-1)][j-1]);}
}
int lcp(int x,int y)
{if(xy) return lcp(y,x);x;int dLog[y1-x];return min(st[x][d],st[y-(1d)1][d]);
}
int main()
{scanf(%d,num);for(int las,i1;inum;i){scanf(%d,mii);--mi[i];L[i]n1;scanf(%d,las);for(int bee,j1;jmi[i];j){scanf(%d,bee);s[n]bee-lasm;lasbee;}R[i]n;}m4000,--n;for(int i2;inum;i) s[L[i]-1]m;SuffixSort();for(int i1;imi[1];i) dp[i]mi[1]1-i;for(int i2;inum;i){for(int jL[i];jR[i];j)for(int kL[i-1];kR[i-1];k)dp[j]max(dp[j],min(dp[k],lcp(Rank[k],Rank[j])));}int ans0;for(int iL[num];iR[num];i) ansmax(ans,dp[i]);printf(%d\n,ans1);return 0;
} 2019.2.1 转载于:https://www.cnblogs.com/butterflydew/p/10347173.html
