SPOJ – Tgotp-Blog

PHRASES - Relevant Phrases of Annihilation

有点难度的sa,把所有的字符串串在一起,然后分段保证段上有长为x的两个子串

首先求出sa,然后再求出height 数组,然后二分答案,对于每段就枚举height差值不超过二分值得段。

然后记录在每一段出现最早与最晚得值(判断有无两个串),然后判断。

搞定。

c++代码如下:[......]

Read more

LCS2 - Longest Common Substring II

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

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

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

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

搞定。

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

Read more

LCS - Longest Common Substring

spoj1811

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

c++代码如下: