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


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

☰ Теория

Для решения этой задачи обычный перебор не подойдет, т.к. асимптотика его будет 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

Вставьте недостающие фрагменты кода
C++
Напишите программу ниже
#include <iostream>
#include <vector>
#include <string>

using namespace std;
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;
}

int main()
{
	string s, t;
	cin >> s >> t;
	s = t + '#' + s;
	vector<int> pi;
	pi = prefix_function(s);
   
      return 0;
}