Cod sursa(job #1294064)

Utilizator ArkinyStoica Alex Arkiny Data 16 decembrie 2014 22:16:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<fstream>
#include<string.h>
using namespace std;

int prefix[2000000];
char s[2000000];
char subs[2000000];
int rez[1000];
int nr=0;

ofstream out("strmatch.out");
ifstream in("strmatch.in");

void KMP_Prefix(char s[],int prefix[])
{
	int L=strlen(s);
	prefix[0]=-1;
	int a=-1;
	for(int b=1;b<L;b++)
	{
		if(a>-1 && s[a+1]!=s[b])
			a=prefix[a];
		else if(s[a+1]==s[b])
			a++;
		prefix[b]=a;
	}

}

void KMP(char s[],char subs[])
{
	int N=strlen(s);
	int M=strlen(subs);

	int i=0,j=0;

	KMP_Prefix(subs,prefix);

	while(i<N)
	{
		while(j<M && s[i]==subs[j])
		{
			i++,j++;
		}

		if(j==M)
		{
		  if(nr<1000)
		  {
			rez[nr]=i-M;
		  }
		  nr++;

			j=prefix[j-1]+1;
		}
		else
		{
		   if(j>0)
             j=prefix[j-1]+1;
		   else
			 i++;
		}

	}


}

int main()
{
	in>>subs;
	in>>s;
	KMP(s,subs);

	out<<nr<<'\n';
	for(int i=0;i<nr && i<1000;i++)
		out<<rez[i]<<' ';
	return 0;

}