【SPOJ1811】LCS

求两个串的最长公共子串

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

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

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

2
说点什么

1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
成员
LCF

%

成员
MasterJH5574

你怎么就这么快呢