【SPOJ1811】LCS

求两个串的最长公共子串

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

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

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

说点什么

2 评论 在 "【SPOJ1811】LCS"

提醒
排序:   最新 | 最旧 | 得票最多
成员

%

成员

你怎么就这么快呢

wpDiscuz