<\/p>\n
http:\/\/vjudge.net\/contest\/view.action?cid=31226#overview
\nSPOJ LCS Longest Common Substring<\/p>\n
SPOJ LCS2\tLongest Common Substring II
\nhttp:\/\/vjudge.net\/problem\/viewProblem.action?id=28017<\/p>\n
\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int N = int(2e5) + 9, Z = 26;\r\n\r\nnamespace SAM{\r\n\r\n int trans[N][Z],par[N],len[N],tail,tot;\r\n char buf[N];\r\n\r\n int new_node(){\r\n RST(trans[tot]);\r\n return tot++;\r\n }\r\n int new_node(int u){\r\n CPY(trans[tot],trans[u]),par[tot]=par[u];\r\n return tot++;\r\n }\r\n#define v trans[u][c]\r\n#define p par[u]\r\n#define pp par[uu]\r\n\r\n int Ext(int c){\r\n\r\n int u = tail, uu = new_node(); len[uu] = len[u] + 1;\r\n while (u && !v) v = uu, u = p;\r\n if (!u && !v) v = uu, pp = 0;\r\n else{\r\n if (len[v] == len[u] + 1) pp = v;\r\n else{\r\n int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;\r\n par[_v] = pp = vv; while (v == _v) v = vv, u = p;\r\n }\r\n }\r\n\r\n return tail = uu;\r\n }\r\n\r\n#define c (*cur - 'a')\r\n#define lenn C\r\n\r\n void Init(){\r\n tail = tot = 0; new_node(), RS(buf); REP_S(cur, buf) Ext(c);\r\n }\r\n\r\n int Spell(){\r\n static int C[N], Q[N]; \/\/RST(C);\r\n REP(i, tot) ++C[len[i]];\r\n REP_1(i, len[tail]) C[i] += C[i-1];\r\n REP(i, tot) Q[--C[len[i]]] = i;\r\n\r\n while (~scanf("%s", buf)){\r\n fill(lenn, lenn+tot, 0); int u = 0, l = 0; REP_S(cur, buf){\r\n while (u && !v) l = len[u = p];\r\n if (u = v) checkMax(lenn[u], ++l);\r\n }\r\n DWN(i, tot, 1){\r\n int u = Q[i]; checkMax(lenn[p], lenn[u]);\r\n checkMin(len[u], lenn[u]);\r\n }\r\n }\r\n int res = 0; FOR(u, 1, tot) checkMax(res, len[u]);\r\n return res;\r\n }\r\n\r\n} using namespace SAM;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n Init(), OT(Spell());\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[34],"tags":[],"class_list":["post-930","post","type-post","status-publish","format-standard","hentry","category-34"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-f0","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/930","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=930"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/930\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}