给定一个字符串 $S$，定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串，求每个位置的识别子串的长度。

给出 $n$ 个字符串，再给出 $n$ 个字符串，求一一匹配情况下 LCP 的最大长度和。

求一个回文串，使得这个回文串的一半也是回文串，输出其最长长度。

给定一个字符串，要求支持两种操作，在当前字符串后加入一个字符串，询问字符串 $s$ 在当前字符串中出现了几次？

后缀自动机的做法相信大家都会，这里记录一下后缀数组做法。

给定两个由 A，B 组成的字符串 $S, T$，其中字符 A 可以变为 BB，B 可以变为 AA，AAA 和 BBB 可以被删掉，询问 $S$ 中的一个给定子串能否变为 $T$ 中的一个给定子串。

CJB 天天要跟妹子聊天，可是他对微信的加密算法表示担心：“微信这种加密算法，早就过时了，我发明的加密算法早已风靡全球，安全性天下第一！”

CJB 是这样加密的：设 CJB 想加密的信息有 $m$ 个字节。首先，从网上抓来一张 $n(n \geq m)$ 个字节的图片，分析里面的每个字节(byte)。每个字节有 $8$ 位(bit)二进制数字。他想替换掉某些字节中最低位的二进制数字，使得这张图片中，连续 $m$ 个字节恰为他想加密的信息。这样，图片看起来没什么区别，却包含了意味深长的信息。

很显然，不是所有的图片都能让 CJB 加密他那 $m$ 个字节的信息。他想请你帮忙写个程序判断这张图片是否能加密指定的信息。如果可以加密，则 CJB 要求改变最少的字节数。如果仍有多种解，他希望信息在图片中的位置越前越好。

这里保存一些后缀自动机常见应用和例题，不断完善中，更多的还是看补档计划吧……

A string is finite sequence of characters over a non-empty finite set Σ.

In this problem, Σ is the set of lowercase letters.

Substring, also called factor, is a consecutive sequence of characters occurrences at least once in a string.

Now your task is simple, for two given strings, find the length of the longest common substring of them.

Here common substring means a substring of two or more strings.

Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured new necklaces and bracelets every day. One day she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace.

The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads.

The description of the necklace is a string A = a1a2 … am specifying sizes of the particular beads, where the last character am is considered to precede character a1 in circular fashion.

The disjoint point i is said to be worse than the disjoint point j if and only if the string aiai+1 … ana1 … ai-1 is lexicografically smaller than the string ajaj+1 … ana1 … aj-1. String a1a2 … an is lexicografically smaller than the string b1b2 … bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi

后缀自动机学习总结

前置技能

有限状态自动机

有限状态自动机 DFA，功能就是识别字符串，令一个自动机 $A$，若能识别字符串 $S$，就记为 $A(S) = true$，否则 $A(S) = false$。自动机由五个部分组成，$alpha$ 为字符集，$state$ 状态集合，$init$ 初始状态，$end$ 结束状态集合，$trans$ 状态转移函数。

$tarns(s, ch)$ 表示当前状态是 $s$，在读入后字符 $ch$ 后所到达的状态；同时 $tarns(s, str)$ 表示当前状态是 $s$，在读入后字符串 $str$ 后所到达的状态。

如果 $trans(s, ch)$ 这个转移不存在，我们设其为 null，同时 null 只能转移到 null，null 表示不存在的状态。

兔子们在玩 $k$ 个串的游戏。首先，它们拿出了一个长度为 $n$ 的数字序列，选出其中的一
个连续子串，然后统计其子串中所有数字之和（注意这里重复出现的数字只被统计一次）。

兔子们想知道，在这个数字序列所有连续的子串中，按照以上方式统计其所有数字之和，第
$k$ 大的和是多少。

兔子们在玩两个串的游戏。给定两个字符串 $S$ 和 $T$，兔子们想知道 $T$ 在 $S$ 中出现了几次，
分别在哪些位置出现。注意 $T$ 中可能有“?”字符，这个字符可以匹配任何字符。

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合S，然后它们定义一个字
符串为“好”的，当且仅当它可以被分成非空的两段，其中每一段都是字符串集合S中某个字符串的前缀。
比如对于字符串集合 {“abc”,”bca”}，字符串 “abb”，”abab”是“好”的（”abb”=”ab”+”b”,abab=”ab”+”ab”），而字符串“bc”不是“好”的。

兔子们想知道，一共有多少不同的“好”的字符串。

Om Nom knows that his girlfriend loves beautiful patterns. That’s why he wants the beads on the necklace to form a regular pattern. A sequence of beads S is regular if it can be represented as S = A + B + A + B + A + … + A + B + A, where A and B are some bead sequences, “ + “ is the concatenation of sequences, there are exactly 2k + 1 summands in this sum, among which there are k + 1 “A” summands and k “B” summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn’t mind if A or B is an empty sequence.

顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。
输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。