Cod sursa(job #574352)

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

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

int NA, NB, P[DIM], R[1001];
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[++R[0]] = i - NA + 1;
			if (R[0] == 1000)
				break;
		}
	}	
	
	fo << R[0] << '\n';
	for (i = 1; i <= R[0]; i++)
		fo << R[i] << ' ';
	return 0;
}