Cod sursa(job #574382)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 7 aprilie 2011 09:30:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include <fstream>
#include <string>
using namespace std;
#define DIM 2000005

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

int NA, NB, P[DIM], R[1005];
char A[DIM], B[DIM];

int main()
{
	int i, k;
	
	fi >> A + 1 >> B + 1; 
	NA = strlen(A + 1) + 1;
	NB = strlen(B + 1) + 1;
	
	k = 0;
	P[1] = 0;
	for (i = 2; i < NA; i++)
	{
		while (k > 0 && A[k+1] != A[i])
			k = P[k];
		if (A[k+1] == A[i])
			k++;
		P[i] = k;
	}
	
	k = 0;
	for (i = 1; i < NB; i++)
	{
		while (k > 0 && A[k+1] != B[i])
			k = P[k];
		if (A[k+1] == B[i])
			k++;
		if (k == NA - 1 && R[0] < 1000)
			R[++R[0]] = i - NA + 1;
	}	
	
	fo << R[0] << '\n';
	if (R[0] > 1000) R[0] = 1000;
	for (i = 1; i <= R[0]; i++)
		fo << R[i] << ' ';
	fo << '\n';
	return 0;
}