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

通常情况下，我们可以使用函数 $toupper()$ 和 $tolower()$ 来实现字母大小写的转化，但在需要常数优化的情况下，这是较慢的。

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

KMP算法学习总结

KMP（Knuth-Morris-Pratt）是一种改进的字符串匹配算法，也是算法竞赛中常用的字符串匹配算法之一，它可以有效地利用失配信息来使得匹配全过程中不回溯，从而在线性时间内完成匹配。

字符串Hash学习总结

定义

字符串Hash简单来说就是：把字符串有效地转换为一个整数。

Hash函数

就是使得每一个字符串都能够映射到某一个整数上的函数