wordpress滑块代码,seo外链增加,东莞建筑建设网站建设,网站给假冒伪劣产品做推广题目链接 POJ2774SPOJ1811 LCS - Longest Common Substring 比后缀自动机慢好多(废话→_→)。 \(Description\) 求两个字符串最长公共子串 \(Solution\) 任何一个子串一定是某个后缀的前缀 可以将两个字符串拼在一起#xff0c;中间用一个从未出现过的字符隔开#xff0c;这样… 题目链接 POJ2774SPOJ1811 LCS - Longest Common Substring 比后缀自动机慢好多(废话→_→)。 \(Description\) 求两个字符串最长公共子串 \(Solution\) 任何一个子串一定是某个后缀的前缀 可以将两个字符串拼在一起中间用一个从未出现过的字符隔开这样ht[]的最大值就是答案 不一定最大的ht[]可能是由同一个字符串得到的判一下属于哪个字符串即可 //3772K 516MS
//SPOJ:26M 0.11s(N5e5)
#include cstdio
#include cstring
#include algorithm
const int N2e510;int n,l,sa[N],rk[N],ht[N],sa2[N],tm[N];
char s[N];void Get_SA()
{int *xrk,*ysa2,m30;for(int i1; in; i) tm[x[i]s[i]-a1];for(int i1; im; i) tm[i]tm[i-1];for(int in; i; --i) sa[tm[x[i]]--]i;for(int p0,k1; kn; mp,p0,k1){for(int in-k1; in; i) y[p]i;for(int i1; in; i) if(sa[i]k) y[p]sa[i]-k;for(int i0; im; i) tm[i]0;for(int i1; in; i) tm[x[i]];for(int i1; im; i) tm[i]tm[i-1];for(int in; i; --i) sa[tm[x[y[i]]]--]y[i];std::swap(x,y), px[sa[1]]1;for(int i2; in; i)x[sa[i]]y[sa[i-1]]y[sa[i]]y[sa[i-1]k]y[sa[i]k]?p:p;if(pn) break;}for(int i1; in; i) rk[sa[i]]i;ht[1]0;for(int k0,p,i1; in; i){if(rk[i]1) continue;if(k) --k;psa[rk[i]-1];while(iknpkns[ik]s[pk]) k;ht[rk[i]]k;}
}int main()
{scanf(%s,s1), lstrlen(s1);s[l1]z1;scanf(%s,s2l), nstrlen(s1);Get_SA();int res0;for(int i2; in; i)if((sa[i]l)^(sa[i-1]l)) resstd::max(res,ht[i]);printf(%d,res);return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8569707.html
