Cod sursa(job #1496897)

Utilizator ArkinyStoica Alex Arkiny Data 5 octombrie 2015 18:59:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>
#include<string.h>
using namespace std;

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

#define MAX 2000001

char A[MAX], B[MAX];
int prefix[MAX],v[1001],N=0;

void make_prefix()
{
	int l = strlen(A);
	int i = 0,j=1;
	
	while (j < l)
	{
		if (A[i] == A[j])
			prefix[j++] = ++i;
		else if (i>0)
			i = prefix[i - 1];
		else
			prefix[j++] = i;

	}

}


void KMP()
{
	int l_A = strlen(A);
	int l_B = strlen(B);

	make_prefix();

	int i = 0, j = 0;

	while (j < l_B)
	{
		if (A[i] == B[j])
			++i, ++j;
		else if (i>0)
			i = prefix[i - 1];
		else
			++j;

		if (i == l_A)
		{
			++N;
			if (N <= 1000)
				v[N] = j - l_A;

			i = prefix[i - 1];
		}
			
	}


}

int main()
{
	in >> A;
	in >> B;
	KMP();
	out << N <<'\n';
	for (int i = 1;i <= N && i <= 1000;++i)
		out << v[i]<<" ";
	return 0;
}