Префикс-функция, Z-функция


Для решения этой задачи обычный перебор не подойдет, т.к. асимптотика его будет O(t*s). Поэтому для задач с поиском подстроки применяют алгоритм КМП (Кнута-Морриса-Пратта).
Для реализации этого алгоритма используется префикс-функция строки, это массив чисел длиной n (длина строки 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.

 

Задача для тренировки:

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

Проведя оптимизацию префикс-функции (подробнее здесь ), получим итоговый алгоритм с асимптотикой O(n):

vector<int> prefix_function (string s) {
	int n = (int) s.length();
	vector<int> pi (n);
	for (int i=1; i<n; ++i) {
		int j = pi[i-1];
		while (j > 0 && s[i] != s[j])
			j = pi[j-1];
		if (s[i] == s[j])  ++j;
		pi[i] = j;
	}
	return pi;
}

Задача для тренировки:

Префикс-функция

Z-функция
Z-функция от строки S - массив Z, каждый элемент которого Z[i] равен длиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки Z. Значение Z-функции в нулевой позиции обычно равно или нулю, или длине всей строки.
Сложность
O(|S| ^ 2) или O(|S|).
 
Префикс-функция от строки S - массив P, каждый элемент которого P[i] равен длиннейшему суффиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и суффиксом всей строки S. Значение P-функции в нулевой позиции обычно равно или нулю, или длине всей строки. 
Сложность
O(|S| ^ 2) или O(|S|).
 
Попробуйте сами реализовать Z-функцию и префикс-функцию за O(|S| ^ 2).

Задача для тренировки:

Z-функция

 
И Z, и префикс функции могут использоваться для реализации алгоритма КМП(Кнута-Морриса-Пратта), предназначенного для поиска подстроки в строке за O(|S|). Суть этого алгоритма такова: приписываем к строке, которую мы хотим найти, строку, в которой ведется поиск. Очень желательно между этими строками поставить разделительный символ, т. е. символ, который не встречается ни в одной строке (обычно #).

Задача для тренировки:

Cipher