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