Cod sursa(job #3202907)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 12 februarie 2024 17:03:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
// #include <iostream>

#include <fstream>
#include <string>
#include <vector>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

vector<int>match;
int lps[2000005];

int main()
{
	string main, pattern;
	getline(cin, pattern);
	getline(cin, main);
	int n = main.size();
	int m = pattern.size();
	int q = 0;
	for (int i = 2; i <= m; i++)
	{
		while (q && pattern[q] != pattern[i - 1])
			q = lps[q];
		if (pattern[q] == pattern[i - 1])
			q++;
		lps[i] = q;
	}
	q = 0;
	for (int i = 1; i <= n; i++)
	{
		while (q && pattern[q] != main[i - 1])
			q = lps[q];
		if (pattern[q] == main[i - 1])
			q++;
		if (q == m)
		{
			q = lps[q];
			match.push_back(i-m);
		}
	}
	cout << match.size() << '\n';
	for (int i = 0; i < match.size(); i++)
		cout << match[i] << ' ';
	return 0;
}