给定一个字符串 $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

兔子们在玩字符串的游戏。首先，它们拿出了一个字符串集合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都是回文串。

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

小t非常感谢大家帮忙解决了他的上一个问题。然而病毒侵袭持续中。在小t的不懈努力下，他发现了网路中的“万恶之源”。这是一个庞大的病毒网站，他有着好多好多的病毒，但是这个网站包含的病毒很奇怪，这些病毒的特征码很短，而且只包含“英文大写字符”。当然小t好想好想为民除害，但是小t从来不打没有准备的战争。知己知彼，百战不殆，小t首先要做的是知道这个病毒网站特征：包含多少不同的病毒，每种病毒出现了多少次。大家能再帮帮他吗？

In the Christian religion, the Trinity is the union of the Father, the Son, and the
Holy Spirit in one God. Recently in a far-far-away country, a new word “Hrinity” was
created and became very popular. “Hrinity” means “The son is the father, and the
father is the son.” But the word “Hrinity” has nothing to do with God or any religion.
It’s about a writer and his son.
When the son was in high school, he failed all exams of all courses. As a none
famous writer, the son’s worrying father carried out a bold plan: he wrote a long novel
and declared that it’s his 16 year old son’s work. An idiot kid can write a long novel?
That made a press interested and the press published the novel. Since then, the son got
famous and rich, and his father has been keep writing novels and articles on his son’s
name.

给出一个字母地图和一些字符串，请你找出每个字符串的第一个字母在地图中的位置和该字符串的方向。
假设地图左上角为原点（0,0）。可能的方向有8个，从北开始顺时针方向依次编号A～H，北方编号为“A”。

After observing the results of Spy Syndrome, Yash realised the errors of his ways. He now believes that a super spy such as Siddhant can’t use a cipher as basic and ancient as Caesar cipher. After many weeks of observation of Siddhant’s sentences, Yash determined a new cipher technique.

For a given sentence, the cipher is processed as:

Doubleville, a small town in Texas, was attacked by the aliens. They have abducted some of the residents and taken them to the a spaceship orbiting around earth. After some (quite unpleasant) human experiments, the aliens cloned the victims, and released multiple copies of them back in Doubleville. So now it might happen that there are 6 identical person named Hugh F. Bumblebee: the original person and its 5 copies. The Federal Bureau of Unauthorized Cloning (FBUC) charged you with the task of determining how many copies were made from each person. To help you in your task, FBUC have collected a DNA sample from each person. All copies of the same person have the same DNA sequence, and different people have different sequences (we know that there are no identical twins in the town, this is not an issue).

Given two strings a and b we define ab to be their concatenation. For example, if a = “abc” and b = “def” then a*b = “abcdef”. If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = “” (the empty string) and a^(n+1) = a(a^n).

Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, “Can you propose an efficient algorithm to find the length of the largest palindrome in a string?”

A string is said to be a palindrome if it reads the same both forwards and backwards, for example “madam” is a palindrome while “acm” is not.

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter ‘e’. He was a member of the Oulipo group. A quote from the book:

Tout avait Pair normal, mais tout s’affirmait faux. Tout avait Fair normal, d’abord, puis surgissait l’inhumain, l’affolant. Il aurait voulu savoir où s’articulait l’association qui l’unissait au roman : stir son tapis, assaillant à tout instant son imagination, l’intuition d’un tabou, la vision d’un mal obscur, d’un quoi vacant, d’un non-dit : la vision, l’avision d’un oubli commandant tout, où s’abolissait la raison : tout avait l’air normal mais \cdots

Given a string of length at most $100,000$ consist of alphabets and numbers. Output the suffix array of the string.
A suffix array is an array of integers giving the starting positions $(0-based)$ of suffixes of a string in lexicographical order. Consider a string $”abracadabra0AbRa4Cad14abra”$. The size of the suffix array is equal to the length of the string. Below is the list of $26$ suffixes of the string along with its starting position sorted in lexicographical order:

$FJ$ 打算带他的 $N(1 \leq N \leq 30,000)$ 头奶牛去参加一年一度的“全美农场主大奖赛”。在这场比赛中，每个参赛者都必须让他的奶牛排成一列，然后领她们从裁判席前依次走过。 今年，竞赛委员会在接受队伍报名时，采用了一种新的登记规则：他们把所有队伍中奶牛名字的首字母取出，按它们对应奶牛在队伍中的次序排成一列（比如说，如果 $FJ$ 带去的奶牛依次为 Bessie、Sylvia、Dora，登记人员就把这支队伍登记为 $BSD$）。登记结束后，组委会将所有队伍的登记名称按字典序升序排列，就得到了他们的出场顺序。 $FJ$ 最近有一大堆事情，因此他不打算在这个比赛上浪费过多的时间，也就是说，他想尽可能早地出场。于是，他打算把奶牛们预先设计好的队型重新调整一下。 $FJ$ 的调整方法是这样的：每次，他在原来队列的首端或是尾端牵出一头奶牛，把她安排到新队列的尾部，然后对剩余的奶牛队列重复以上的操作，直到所有奶牛都被插到了新的队列里。这样得到的队列，就是FJ拉去登记的最终的奶牛队列。 接下来的事情就交给你了：对于给定的奶牛们的初始位置，计算出按照 $FJ$ 的调整规则所可能得到的字典序最小的队列。

把一个字符串 $S$ 排成一圈，从每个字符开始读一圈，把每次读到的字符串排序，按顺序将每个串的最后一个字符排成一个新字符串，求新字符串。

链接

BZOJ1031

解密

题目描述

为了保密，QW 星球使用了特殊的指令，指令以字符的形式发出，并且应用了加密策略。现在，他们的加密规则被我们熟悉，原来规则如此有趣：将所有 a～z 或 A～Z 字母变成它的后继，例如“A”变成“B”，“a”变成“b”,“Z”变成“A”，“z”变成“a”，其他非字母的字符保持不变。现在请你破译接收到的一串指令。

字符个数

题目描述

输入一串字符，以“?”结束。分别统计其中字母的个数,数字个数和其它符号的个数。
其中字母个数是指大,小写字母的总数，及 A—— Z 和 a —— z；
其中数字指从 0—— 9 范围的数字。
三个统计数字在一行，分别用一个空格隔开，“？”不参与统计。

数字分离

题目描述

给定一个有6位数字的正整数，请你把它每位数字分离出来并求和。

输入格式

输入文件只有一个6位数字的正整数。

输出格式

输出文件有一个正整数，即分离出来每位数字之和。

单词

题目背景

TJOI2013 DAY1 T3

题目描述

小张最近在忙毕业论文设计，所以一直在读论文。一篇论文是由许多单词组成的。
但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现多少次。

输入格式

第一行一个整数 N (N \leq 200)，表示有 N 个单词。接下来 N 行每行一个单词。每个单词都由小写字母（’a’～’z’）组成。
所有单词构成论文（一行一个单词）。

输出格式

输出 N 个整数，第 i 行的数字表示第 i 个单词在文章中出现了多少次。

统计难题

题目背景

HDU 1251

题目描述

Ignatius 最近遇到一个难题，老师交给他很多单词(只有小写字母组成，不会有重复的单词出现)，现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀)。

输入格式

输入数据的第一部分是一张单词表（不超过 $10^4$ 个单词），每行一个单词，单词的长度不超过 10，它们代表的是老师交给 Ignatius 统计的单词，一个空行代表单词表的结束。第二部分是一连串的提问，每行一个提问，每个提问都是一个字符串（不超过 $10^4$ 个提问串）。
注意:本题只有一组测试数据，处理到文件结束。

Phone List

题目背景

HDU 1671

题目描述

给出一份电话号码列表，如果不存在有一个号码是另一个号码的前缀，我们就说这份电话号码列表是合法的。让我们看看如下号码列表：

1. Emergency 911
2. Alice 97625999
3. Bob 91125426

在这组号码中，我们不能拨通 Bob 的电话，因为当你按下 Bob 电话号码的前 $3$ 个数字 911 时，电话局会把你的拨号连接到 Emergency 的线路。

所以这组号码是不合法的。

最长子串

题目描述

给出一个全部由小写字母构成的字符串，要求从该串中找出满足下面条件的最长子串：

条件1：子串是连续的；

条件2：子串的长度是偶数；

条件3：沿子串的中心切开，对左右两部分的串按顺序进行比较，要求不同的字符对数 $N$ 不超过题目给出的一个限定值 $D$。
比如：abcaec 的 $N$ 值为 $1$。因为平分的两部分 abc 和 aec 比较，只有 $1$ 对字符不同：即 b 和 e，而其余字符都相同。

Shortest Prefixes

题目背景

POJ 2001

题目描述

给出 $n$ 个单词（$1 \leq n \leq 1000$），求出每个单词的非公共前缀，如果没有，则输出自己。

输入格式

输入 N 个单词，每行一个，每个单词都是由 1～20 个小写字母构成。

输出格式

输出 N 行，每行由一个空格的两部分，第一部分是输入的单词，第二部分是该单词在所有单词中的非公共前缀，如果没有，则输出自己。