Cod sursa(job #792594)

Utilizator mihai96alexOprea Mihai Alexandru mihai96alex Data 27 septembrie 2012 20:57:59
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<fstream>
#include<cstring>
using namespace std;

ifstream fin("kmp.in");
ofstream fout("kmp.out");
int m,n,k,pi[100],q,x,v[1001];
char M[100],N[100];

int main()
{
	int i;
	fin>>N;fin>>M;
	n=strlen(N);
	m=strlen(M);
	for(i=n;i>=1;--i) N[i]=N[i-1];
	for(i=m;i>=1;--i) M[i]=M[i-1];
	k=0;
	pi[1]=0;
	for(i=2;i<=n;++i)
	{											//functia prefix
		while(k>0 && N[k+1]!=N[i])
			k=pi[k];
		if(N[k+1]==N[i]) k++;
		pi[i]=k;
	}											
	q=0;
	for(i=1;i<=m;++i)
	{
		while(q>0 && N[q+1]!=M[i])
			q=pi[q];
		if(N[q+1]==M[i])
			q++;
		if(q==n)
		{
			x++;
			if(x<=1000)
			v[x]=i-n;
		}
	}
	fout<<x<<"\n";
	for(i=1;i<=x;++i)
		fout<<v[i]<<" ";

}