Cod sursa(job #806652)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 3 noiembrie 2012 11:11:29
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
using namespace std;

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

const int dim = 4000005; 
char S[dim];
int P[dim], R[1005], N, len;

void cit ()
{
	S[0] = '#';
	fi >> S + 1;
	while (S[len] != 0) len++;
	S[len] = '#';
	fi >> S + len + 1;	
	len--;
}

void kmp ()
{
	int k = 0;
	P[0] = 0;
	for (int i = 2; S[i] != 0; i++)
	{
		while (k > 0 && S[k + 1] != S[i])
			k = P[k];
		if (S[k + 1] == S[i])
			k++;
		P[i] = k;
		
		if (P[i] == len)
		{
			N++;
			if (N <= 1000)
				R[++R[0]] = i - len - len - 1;
		}
	}
}

void afi ()
{
	fo << N << '\n';
	for (int i = 1; i <= R[0]; i++)
		fo << R[i] << ' ';	
}

int main ()
{
	cit ();
	kmp ();
	afi ();
	return 0;
}