Cod sursa(job #2472374)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 12 octombrie 2019 11:58:19
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <string>
#define NMAX 100010

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string s, a;
int prefix[NMAX];
vector<int> sol;

void makePrefix()
{
	int q = 0;
	prefix[1] = 0;
	for (int i = 2; i < s.size(); i++)
	{
		while (q && s[i] != s[q + 1])
			q = prefix[q];
		if (s[i] == s[q+1])
			q++;
		prefix[i] = q;
	}
}

int main()
{
	fin >> s >> a;
	s = "#" + s;
	a = "#" + a;
	makePrefix();
	int N = s.size() - 1;
	int M = a.size() - 1;
	int q = 0;

	for (int i = 1; i <= M; i++)
	{
		while (q && s[q + 1] != a[i])
			q = prefix[q];
		if (s[q + 1] == a[i])
			q++;
		if (q == N)
		{
			sol.push_back(i-N+1);
			q = prefix[N];
		}
	}
	fout << sol.size() << '\n';

	for (int i = 0; i < sol.size() && i < 1000; i++)
	{
		fout << sol[i]-1 << ' ';
	}



	return 0;
}