【SPOJ1812】LCS2

多串的最长公共子串

我们仍然对其中一个建后缀自动机,再拿另外的串分别在后缀自动机上面跑。因为每个串包含的子串是不同的,所以我们要把信息记录在后缀自动机上。对于每一个在后缀自动机上跑过的串,记录它在每个点时的最大匹配长度。那么我们就可以知道每个点表示的串中哪些出现了。同时我们沿\(fail\)链将最大匹配长度上传(如果非\(0\)),因为\(fail\)链上的父亲一定是其后缀,一定也都出现了,所以父亲的最大匹配长度直接等于其\(len\)值即可。

说点什么

  Subscribe  
提醒