Cod sursa(job #574481)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 7 aprilie 2011 11:07:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include <cstring>

using namespace std;

const char InFile[]="strmatch.in";
const char OutFile[]="strmatch.out";
const int MaxN=2000111;
const int MaxSol=1024;

ifstream fin(InFile);
ofstream fout(OutFile);

int n,m,sol,vsol[MaxSol],p[MaxN];
char N[MaxN],M[MaxN];

inline void prefix()
{
	m=strlen(M+1);
	int k=0;
	p[1]=0;
	for(register int i=2;i<=m;++i)
	{
		while(k>0 && M[k+1]!=M[i])
		{
			k=p[k];
		}
		if(M[k+1]==M[i])
		{
			++k;
		}
		p[i]=k;
	}
}

inline void kmp()
{
	n=strlen(N+1);
	int q=0;
	for(register int i=1;i<=n;++i)
	{
		while(q>0 && N[i]!=M[q+1])
		{
			q=p[q];
		}
		if(N[i]==M[q+1])
		{
			++q;
		}
		if(q==m)
		{
			++sol;
			if(sol<=1000)
			{
				vsol[sol]=i-m+1;
			}
		}
	}
}

int main()
{
	fin>>(M+1);
	fin>>(N+1);
	fin.close();
	
	prefix();
	kmp();

	fout<<sol<<"\n";
	int x=min(1000,sol);
	for(register int i=1;i<=x;++i)
	{
		fout<<vsol[i]-1<<" ";
	}
	fout.close();
	return 0;
}