Cod sursa(job #587565)

Utilizator loginLogin Iustin Anca login Data 5 mai 2011 10:25:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
# include <fstream>
# include <iostream>
# include <cstring>
# define DIM 2000003
# define min(a,b) (a<b?a:b)
using namespace std;
int np, v[DIM], t[DIM], ls, lw;
char s[DIM], w[DIM]; 

void read ()
{
	ifstream fin ("strmatch.in");
	fin.getline(w,DIM);
	fin.getline(s,DIM);
	ls=strlen(s);
	lw=strlen(w);
}

void calc ()
{	
	int p=0;
	t[0]=-1;t[1]=0;
	for(int i=2;i<lw;)
		if (w[i-1]==w[p])
			++p, t[i]=p, ++i;
		else if (p)
			p=t[p];
		else
			t[i]=0, ++i;
}

void KMP ()
{
	calc();
	int i=0;
	for(int m=0;m<ls;)
		if (s[m+i]==w[i])
		{
			if (i+1==lw)
			{
				v[++np]=m;
				m+=i-t[i];
				if (t[i]>-1)i=t[i];
				else i=0;
			}
			else
				++i;
		}
		else
		{
			m+=i-t[i];
			if (t[i]>-1)i=t[i];
			else i=0;
		}
}

int main()
{
	read ();
	KMP();
	freopen("strmatch.out", "w", stdout);
	printf("%d\n", np);
	for(int i=1;i<=min(1000,np);++i)
		printf("%d ", v[i]);
	return 0;
}