Олимпиадный тренинг

Задача . Поиск подстроки, КМП, тривиальный вариант: Начало

Задача

Темы:

Найти все вхождения строки t в строке s.

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

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

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

В ответе нужно вывести все вхождения строки t в строку s в порядке возрастания. Нумерация позиций строк начинается с нуля.

Ввод	Вывод
abababcab abab	0 2

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

Статистика успешных решений по компиляторам

Комментарий учителя

Ваш ответ

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; }

Напишите программу ниже

#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;
}

Загруженные файлы

Нет