sam – Tgotp-Blog

#2479. 「九省联考 2018」制胡窜

写起来复杂,但是说起来并不复杂的一道题。。。

首先这题如果直接考虑满足条件的会发现极为毒瘤。

反过来考虑用总方案-不满足条件的就会友好的多。

考虑如何求不满足条件的。

发现实际上本质就是用两条线穿过所有的串s_{l,r}

设现在有m个串,第i串的[......]

Read more

审判

伢正在审问你,而想打动她没那么容易。

你想将你们怪盗做过的事情都告诉伢,澄清自己。怪盗们经历过的所有事件抽象成一个⻓度为n的字符串(仅包含a,b,c 三种字符)。

伢为了检验你是否是在编故事,会向你提出q次询问,
第i次询问给出l与r ,表示询问[l,r] 这段时间你们所做的事情在所有[......]

Read more

2780: [Spoj]8093 Sevenk Love Oimaster

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

c++代码如下:

 

LCS2 - Longest Common Substring II

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

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

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

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

搞定。

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

Read more

LCS - Longest Common Substring

spoj1811

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

c++代码如下: