给定一个字符串 $S$，定义一个位置 $i$ 的识别子串为包含这个位置且在原串只出现一次的字符串，求每个位置的识别子串的长度。
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)$ 这个转移不存在，我们设其为
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.
Update your browser to view this website correctly. Update my browser now