Cod sursa(job #2780322)

Utilizator bubblegumixUdrea Robert bubblegumix Data 6 octombrie 2021 18:15:04
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<iostream>
#include<string>
#include<vector>
using namespace std;
const int lim = 2e6 + 5;
string pat;
string txt;
vector<int>sol;
int kmp[lim];
void preprocess()
{
	int curr = 0;
	for (int i = 1; i < pat.size(); i++)
	{
		while (curr && pat[curr] != pat[i])
			curr = kmp[curr-1];
		if (pat[i] == pat[curr])
			curr++;
		kmp[i] = curr;
	}
}
void match()
{
	int j = 0;
	for (int i = 0; i < txt.size(); i++)
	{
		while (j && pat[j] != txt[i])
			j = kmp[j - 1];
		if (pat[j] == txt[i])
			j++;
		if (j == pat.size())
		{
			sol.push_back(i-j+1);
			j = kmp[j-1];
		}
			
	}

}
int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	cin >> pat;
	cin >> txt;
	preprocess();
	match();
	cout << sol.size() << '\n';
	for (int i = 1; i <= min((int)sol.size(), 1000); i++)
		cout << sol[i - 1] << " ";
}