Cod sursa(job #856719)

Utilizator ioanapopaPopa Ioana ioanapopa Data 16 ianuarie 2013 21:14:43
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include<cstdio>
#include<string.h>
#include<fstream>
#define dim 2000001

using namespace std;

int p[1000],poz[dim];
int m,n,x;
char a[dim],b[dim];

void KMP_calcul()
{
	int k = 0;
	p[1] = 0;
	for(int i = 2 ; i<=m; i++)
	{
		while( (k > 0) && (b[k+1] != b[i]))
			k = p[k];
		if(b[k+1] == b[i])
			k++;
		p[i] = k;
	}
}

void KMP_potrivire()
{
	int q = 0;
	for(int i = 1; i<=n ; i++)
	{
		while((q>0) && (a[i] != b[q+1]))
			q = p[q];
		if(a[i] == b[q+1])
			q++;
		if(q==m)
		{
			if(x<1000)
				poz[x] = i - m;
			x++;
			q = p[q];
			
		}
	}
}
			
	
int main()

{	
	ifstream f("grader_test38.in");
	ofstream g("strmatch.out");
	
	f >> (b+1) >> (a+1);
	
	n = strlen(a+1);
	m = strlen(b+1);
	
	KMP_calcul();
	KMP_potrivire();
	
	g << x << "\n";
	if(x > 1000)
		x = 1000;
	for(int i = 0 ; i < x; i++)
		g << poz[i] <<" ";
	
	return 0;
}