# 「BJ模拟」图片加密-kmp+FFT

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

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

# 「SPOJ-1811」LCS-后缀自动机

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.

# 「POJ1509」Glass Beads-后缀自动机

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

# 「CF-526D」Om Nom and Necklace-后缀数组

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.

# 「CF-17E」Palisection-乱搞

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.

# 「POJ-4052」Hrinity-AC自动机

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.

# 「CF-633C」Spy Syndrome 2-Hash+map

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:

# 「POJ-2945」Find the Clones-map

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).

# 「POJ-1523」Power Strings-KMP

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).

# 「POJ-3974」Palindrome-manacher

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.

# 「HDU-2222」Keywords Search-AC自动机

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.

# 「POJ-3461」Oulipo-KMP

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

# 「SPOJ-SARRAY」-后缀数组-SA-IS

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:

# 「BZOJ-1692」队列变换-后缀数组

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

BZOJ1031

TJOI2013 DAY1 T3

# 「HDU 1251」统计难题

## 统计难题

HDU 1251

### 题目描述

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

# 「HDU 1671」Phone List

## Phone List

HDU 1671

### 题目描述

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

# 「POJ 2001」Shortest Prefixes

## Shortest Prefixes

POJ 2001

### 输出格式

###### Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×