Cod sursa(job #2456823)

Utilizator UnDragosDragos Ioana UnDragos Data 15 septembrie 2019 15:46:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int table[2000005];
int main()
{
	string A, B;
	ios_base::sync_with_stdio(false);
	ifstream cin("strmatch.in");
	//ofstream cout("strmatch.out");
	cin >> A >> B;
	A = " " + A;
	B = " " + B;
	int N = A.size() - 1;
	int M = B.size() - 1;
	table[1] = 0;
	for (int i = 2,k=0; i <= N; ++i)
	{
		while (k !=0 && A[k + 1] != A[i])
		{
			k = table[k];
		}
		if (A[k + 1] == A[i])
		{
			++k;
		}
		table[i] = k;
	}
	vector<int> sol;
	int nr_sol = 0;
	for (int j = 1,i=0; j <= M; ++j)
	{
		while (i > 0 && A[i + 1] != B[j])
		{
			i = table[i];
		}
		if (A[i + 1] == B[j])
		{
			++i;
		}
		if (i == N)
		{
			if (sol.size() < 1000)
			{
				nr_sol++;
				sol.push_back(j - N);
			}
		}
	}
	cout << nr_sol << "\n";
	for (auto i : sol)
		cout << i << " ";
	cout << "\n";
	return 0;

}