Cod sursa(job #2371815)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 6 martie 2019 19:45:24
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>

using namespace std;

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

void precalc();
void kmp();

int n, m, nr, sol[1005], pre[2000005];
char p[2000005], s[2000005];

int main()
{
	int i;

	fin >> p >> s;
	n = strlen(s);
	m = strlen(p);
	kmp();
	fout << nr << '\n';
	for (i = 1; i <= nr; i++)
	{
		if (i > 1000)
			break;
		fout << sol[i] << ' ';
	}
	fout << '\n';
	return 0;
}

void precalc()
{
	int i, lg = 0;

	pre[0] = 0;
	i = 1;
	while (i < m)
	{
		if (p[i] == p[lg])
		{
			lg++;
			pre[i] = lg;
			i++;
		}
		else
		{
			if (lg != 0)
				lg = pre[lg - 1];
			else
			{
				lg = 0;
				i++;
			}
		}
	}
}

void kmp()
{
	int i, j;

	precalc();
	i = j = 0;
	while (i < n)
	{
		if (p[j] == s[i])
		{
			i++;
			j++;
		}

		if (j == m)
		{
			nr++;
			if (nr <= 1000)
				sol[nr] = i-m;
			j = pre[j - 1];
		}
		else if (i < n && p[j] != s[i])
		{
			if (j != 0)
				j = pre[j];
			else i++;
		}
	}
}