【SPOJ1811】LCS

求两个串的最长公共子串

naive的做法很多啊 但是跑的最快的应该是\(O(n)\)的后缀自动机吧

对一个串建后缀自动机,拿另一个在上面跑。每一次有两种情况:当前点就有这个儿子,那么显然直接将当前答案\(+1\),否则不断跳\(fail\)直到一个有这个儿子的位置\(p\),然后将当前答案变为\(len[p]+1\)。仔细想想就能明白两种情况的区别。两种情况均再走向它的这个儿子即可。

我觉得我的改良后的后缀自动机写法应该算是比较优美的了233(主要是短)

Subscribe
提醒
2 评论
最旧
最新 得票最多
Inline Feedbacks
View all comments
LCF
3 年 之前

%

MasterJH5574
3 年 之前
Reply to  LCF

你怎么就这么快呢