Category Archives: 后缀自动机

Codeforces 316G3 Good Substrings

给出一个主串,然后n个串,每个串给出一条限制[l, r]表示某个串s在此串中出现次数在[l, r]之间,求主串 …

CodeForces 204E Little Elephant and Strings (后缀自动机)

给出n个串,计算i串有多少子串在[1, n]个串中至少k个串中出现。 首先我们对n个串建立后缀自动机,同时我们 …

CodeForces 123D String (后缀自动机)

给出一个字符串,假设每个子串si在原串种出现ti次,那么求出所有的si的ti * (ti + 1) / 2的和 …

HDU 5853 Jong Hyok and String

给出n个字符串,m个询问,每个询问给出一个字符串,定义set(string) = { (i, j) | i表示 …

2016 Multi-University Training Contest 4

1001 – Another Meaning 给出A串和B串,可以选择A串中被B串匹配的任意位置打 …

Codeforces 653 F Paper task (后缀自动机,倍增)

给出一个只包含'(‘和’)’的串,问不同的子串并且子串能够符合括号匹配的个 …

HDU 4416 Good Article Good sentence (后缀自动机)

给出n+1个串,求第一个串的不同子串不是其他串的子串的个数。 不妨将对第一个串构造SAM,接着将剩下的n个串去 …

Codeforces 427 D Match & Catch (后缀自动机)

给出两个串,计算两个串最短且只出现一次的lcs的长度。 之前的做法的复杂度接近O(n^2),这次介绍一种O(n …

Codeforces 235C Cyclical Quest (后缀自动机)

这次我还是要纠正下之前写错的博客,我好low啊! 给出一个母串,然后给出n个串,求每个串不同的循环同构串在母串 …

POJ 3415 Common Substrings (后缀自动机)

给出两个串,计算这两个串长度>=k的公共子串的个数。 这题是典型的后缀数组分组+单调栈,这次我从后缀自动 …