Cod sursa(job #2722924)

Utilizator Rares31100Popa Rares Rares31100 Data 13 martie 2021 13:13:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.82 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
int prefix[2000001];
string a, b;

int main()
{
	in >> a >> b;
	a.insert(a.begin(), ' ');
	b.insert(b.begin(), ' ');
	
	for(int i = 2, lung = 0; i <= a.size() - 1; i++)
	{
		while(lung && a[lung + 1] != a[i])
			lung = prefix[lung];
			
		if(a[lung + 1] == a[i])
			lung++;
			
		prefix[i] = lung;
	}
	
	int nrSol = 0;
	queue <int> sol;
	
	for(int i = 1, lung = 0; i <= b.size() - 1; i++)
	{
		while(lung && a[lung + 1] != b[i])
			lung = prefix[lung];
			
		if(a[lung + 1] == b[i])
			lung++;
			
		if(lung == a.size() - 1)
		{
			sol.push(i - a.size() + 1);
			lung = prefix[lung];
			nrSol++;
		}
	}
	
	out << nrSol << '\n';
	for(int i = 1; i <= min(1000, nrSol); i++)
	{
		out << sol.front() << ' ';
		sol.pop();
	}
	
	return 0;
}