sam – Tgotp-Blog

2780: [Spoj]8093 Sevenk Love Oimaster

广义后缀自动机,即把n个主串一起建立后缀自动机,然后对于查找的直接在sam上求就行了。

c++代码如下:

 

LCS2 - Longest Common Substring II

/------SPOJ1812----/

后缀自动机,把第一个串建后缀自动机,后面直接处理就好了。

记录每个点最长能匹配的长度,显然可以转移到pre上(最长后缀。

然后用桶排可以弄出topo序。

搞定。

c++代码如下:
[crayon-5ad8d08f942f280[......]

Read more

LCS - Longest Common Substring

spoj1811

sam--后缀自动机裸题 。
把a串建立后缀自动机,然后对于b串跑一遍就好了,遇到跑不动的就返回pre继续跑

c++代码如下: