Алгоритмы на строках

Мальчик Кирилл написал однажды на листе бумаги строчку, состоящую из больших и маленьких латинских букв, а после этого ушел играть в футбол. Когда он вернулся, то обнаружил, что его друг Дима написал под его строкой еще одну строчку такой же длины. Дима утверждает, что свою строчку он получил циклическим сдвигом строки Кирилла на несколько шагов вправо (циклический сдвиг строки abcde на 2 позиции вправо даст строку deabc).
Однако Дима известен тем, что может случайно ошибиться в большом количестве вычислений, поэтому Кирилл в растерянности – верить ли Диме? Помогите ему! По данным строкам выведите минимальный возможный размер сдвига или -1, если Дима ошибся.

 

Первые две строки входных данных содержат строки Кирилла и Димы, соответственно. Длины строк одинаковы, не превышают 10000 и не равны 0.

 

Выведите единственное число – ответ  на вопрос задачи.
 

 

Примеры

№	Входные данные	Выходные данные
1	zabcd abcdz	4

Строка S была записана много раз подряд, после чего из получившейся строки взяли подстроку и дали вам. Ваша задача определить минимально возможную длину исходной строки S.

 

На вход программы поступает строка, которая содержит только латинские буквы, длина строки не превышает 50000 символов.

 

Требуется вывести одно число – ответ  на вопрос задачи.
 

 

Примеры

№	Входные данные	Выходные данные
1	z	1
2	abcdef	6

Дана непустая строка S, длина которой N не превышает \(10^6\). Будем считать, что элементы строки нумеруются от 1 до N.

 

Для каждой позиции i символа в строке нас будет интересовать подстрока, заканчивающаяся в этой позиции, и совпадающая с некоторым началом всей строки. Вообще говоря, таких подстрок будет несколько, не меньше двух. Самая длинная из них имеет длину i, она нас интересовать не будет. А будет нас интересовать самая длинная из остальных таких подстрок (заметим, что такая подстрока всегда существует — в крайнем случае, если ничего больше не найдется, сгодится пустая подстрока).

 

Значением префикс-функции \(\pi[i]\) будем считать длину этой подстроки.

 

Префикс-функция используется в различных алгоритмах обработки строк. В частности, с её помощью можно быстро решать задачу о поиске вхождения одной строки в другую («поиск образца в тексте»).

 

Требуется для всех i от 1 до N вычислить \(\pi[i]\).

 

Одна строка длины N, \(0 < N <= 10^6\), состоящая из маленьких латинских букв.

 

Выведите N чисел — значения префикс-функции для каждой позиции, разделенные пробелом.
 

 

Примеры

№	Входные данные	Выходные данные
1	abracadabra	0 0 0 1 0 1 0 1 2 3 4

#include <bits/stdc++.h>
main()
{
    std::string s;
    std::cin >> s;
    int n = s.size(), p[50003], j, i = 1;
    for (; i < n; i++)
    {
        j = p[i - 1];
        for (; j && s[i] != s[j]; j = p[j - 1]);
        p[i] = (s[i] == s[j] ? ++j : j);
    }
    std::cout << n - p[n - 1];
}

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки. 

 

Напишите программу, которая берет упакованную строчку и восстанавливает по ней исходную строку.

 

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n - количество повторений символа (целое число от 2 до 99), а A - заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

 

В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).

 

Примеры

 

Ввод	Вывод
3A4B7D	AAABBBBDDDDDDD
22D7AC18FGD	DDDDDDDDDDDDDDDDDDDDDDAAAAAAACFFFFFFFFFF FFFFFFFFGD
95AB	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAB
40AB39A	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA BAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

 

Даны две строки - S и T. Ваша задача по запросам вывести колличество вхождений i-того префикса строки S в строку T.

Входные данные
В первой строке вводится k - количество запросов (\(k <= длина( S)\)), строка S и строка T. Далее вводится k запросов, запрос на количество вхождений i-го префикса строки S в строку T.

Выходные данные

Вывести k строк с ответами на запросы.

Дана строка S. Найдите сумму значений префикс-функции для всех заданных позиций строки S. 

Входные данные

В первой строке входного файла записана строка S (\(1 <= |S| <= 150 000\)) и k (количество заданных позиций).

Далее идут k чисел - позиции, значения префикс-функции которых надо сложить.

Выходные данные

В выходной файл выведите одно число - сумму значений префикс-функции для всех заданных позиций строки S.