Cod sursa(job #1295377)

Utilizator ArkinyStoica Alex Arkiny Data 19 decembrie 2014 13:06:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<fstream>
#include<string.h>
using namespace std;

#define MAX 2000000

int prefix[MAX];
char str[MAX],sub_str[MAX];
int v[1000],nr;

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

void make_prefix(char sub_str[],int prefix[])
{
	int L=strlen(sub_str);
	prefix[0]=0;
	int a=0;

	for(int b=1;b<L;b++)
	{
		while(a>0 && sub_str[a] != sub_str[b])
			 a=prefix[a-1];
		if(sub_str[a]==sub_str[b])
			a++;
		prefix[b]=a;
	}
}

void KMP(char str[],char sub_str[])
{
	int N=strlen(str);
	int M=strlen(sub_str);

	make_prefix(sub_str,prefix);
	int j=0;
	for(int i=0;i<N;i++)
	{
		  while(j>0 && sub_str[j]!=str[i])
			  j=prefix[j-1];
		  if(sub_str[j]==str[i])
			  j++;
		  if(j==M)
		  {
			  if(nr<1000)
			   v[nr]= i-M+1;
			   ++nr;

			  j=prefix[j-1];
		  }
	}

}

int main()
{
	in>>sub_str;
	in>>str;

	KMP(str,sub_str);


	out<<nr<<'\n';

	for(int i=0;i<nr;i++)
		out<<v[i]<<' ';

	out.close();
	in.close();

	return 0;
}