Cod sursa(job #672188)

Utilizator RobertBBadea Corneliu Robert RobertB Data 1 februarie 2012 18:32:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <string.h>
#define MIN(a, b) (a < b ? a : b)
using namespace std;

int v[2000000],sol[1001];
char A[2000000],B[2000000];
int n,m;

void prefix(char* a)
{
	int k = -1, x;
	v[0] = 0;
	for(x = 1; x < m; x++) {
		while(k>0 && A[k+1]!=A[x])
			k = v[k];
		if(A[k+1] == A[x]) 
			k++;
		v[x] = k;
	}
}

int main() 
{
	int i, x = -1, contor = 0;
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(A, 2000000);
	f.getline(B, 2000000);
	n = strlen(A);
	m = strlen(B);
	prefix(B);
	for(i = 0; i < m; i++) {
		while(x > 0 && A[x+1] != B[i])
			x = v[x];
		if(A[x+1] == B[i]) 
			x++;
		if(x == n-1) {
			x=v[x];
			if(contor <= 1000)
				sol[contor] = i - (n-1);
			++contor;
		}
	}
	g<<contor<<"\n";
	for(i=0;i<MIN(contor, 1000); i++) {
		g<<sol[i]<<" ";
	}
}