Cod sursa(job #1698072)

Utilizator ArkinyStoica Alex Arkiny Data 3 mai 2016 16:58:44
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;

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


char s1[2000010], s2[2000010];
int v[1010], p[2000010], nr;
void make_prefix(char s[],int l)
{
	int j=0;

	for (int i = 1;i < l;)
	{
		if(s[i] == s[j])
			p[i++] = ++j;
		else if (j > 0)
			j = p[j - 1];
		else
			p[i++] = 0;
	}

}

void KMP(char s1[], char s2[])
{
	int l1, l2;
	l1 = strlen(s1);
	l2 = strlen(s2);

	make_prefix(s1, l1);

	int j = 0;

	for (int i = 0;i < l2;)
	{
		if (s1[j] == s2[i])
			++i, ++j;
		else if (j > 0)
			j = p[j - 1];
		else
			++i;
		if (j == l1)
		{
			++nr;
			if (nr <= 1000)
				v[nr] = i - j;
			j = p[j - 1];
		}
	}

}

int main()
{
	in >> s1 >> s2;
	
	KMP(s1, s2);
	out << nr << '\n';
	for (int i = 1;i <= 1000 && i <= nr;++i)
		out << v[i] << " ";

	return 0;
}