Cod sursa(job #696533)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 28 februarie 2012 18:53:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <cstring>
#define nmax 2000003
#define wmax  1000
using namespace std;
char a[2000002], b[2000002];
int pi[2000002], r[2000002];
int n, m, nr = 0;
int i, j;
int main() 
{
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f.getline(a,2000002);
	f.getline(b,2000002);
	n = strlen(a); m = strlen(b);

	pi[0] = pi[1] = 0;
	for (i = 1, j = 0; i < n; ++i) 
	{
		while (j > 0 && a[i] != a[j]) j = pi[j];
		if (a[i] == a[j]) ++j;
		pi[i+1] = j;
	}

	for (i = j = 0; i < m; ++i) 
	{
		while (j > 0 && a[j] != b[i]) j = pi[j];
		if (a[j] == b[i]) ++j;
		if (j == n) 
		{
			if (nr < wmax)
				r[nr] = i - n + 1;
			++nr;
			j = pi[j];
		}
	}
	g<<nr<<"\n";
	if (nr > wmax) nr = wmax;
	for (i = 0; i < nr; ++i)
		g<<r[i]<<" ";
return 0;}