Курс: Строки

Модуль: Префикс-функция, Z-функция

Задачи

Задача

1/10

(C++) Поиск подстроки, КМП, тривиальный вариант: Начало

Ограничение по времени: 500 ms
Ограничение по памяти: 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Теория

Для решения этой задачи обычный перебор не подойдет, т.к. асимптотика его будет O(t*s). Поэтому для задач с поиском подстроки применяют алгоритм КМП (Кнута-Морриса-Пратта).
Для реализации этого алгоритма используется префикс-функция строки, это массив чисел длиной (длина строки s), в котором каждый элемент это наибольшая длина наибольшего собственного суффикса подстроки s, совпадающего с её префиксом. Например:
 

Строка Префикс-функция Примечание
abababcab 0 0 1 2 3 4 0 1 2  
abcabcd 0 0 0 1 2 3 0  
aabaaab 0 1 0 1 2 2 3  

Тривиальный алгоритм префикс-функции с асимптотикой О(n^3):

vector<int> prefix_function (string s) {
	int n = (int) s.length();
	vector<int> pi (n);
	for (int i=0; i<n; ++i)
		for (int k=0; k<=i; ++k)
			if (s.substr(0,k) == s.substr(i-k+1,k))
				pi[i] = k;
	return pi;
}

А теперь надо сделать префикс-функцию для строки вида:  t + # + s, где # - это символ-разделитель, которого однозначно нет в тексте.  Анализируя значения префикс-функции после соответствующего символу-разделителю надо заметить, что если полученное значение равно длине искомой подстроки, то найдено ее вхождение. Например, для строки "abababcab" и искомой подстроки "abab", префикс-функция будет:
0 0 1 2 0 1 2 3 4 3 4 0 1 2, отбросим первые 5 элементов, т.к. нам наужен анализ элементов соответствующих строки s:
1 2 3 4 3 4 0 1 2 - здесь есть два случая когда значение равно 4 ( 4-ый и 6-ый ), т.е. длине t,  в результате ответом надо записать: 4 - 4( длина t)  = 0 и 6 - 4 = 2. Видно, что это правильные ответы и строка "абаб" на самом деле является подстрокой в строке "abababcab" в позиции 0 и 2.

 

Задача

Найти все вхождения строки t в строке s.
 
Входные данные
В первой строке  записана строка s, во второй строке записана строка t. Обе строки состоят только из английских букв. Длины строк могут быть в диапазоне от 1 до 50 000 включительно.
 
Выходные данные
В ответе нужно вывести все вхождения строки t в строку s в порядке возрастания. Нумерация позиций строк начинается с нуля.
 

 

Примеры
Входные данные Выходные данные
1
abababcab
abab
0 2