Cod sursa(job #1404255)

Utilizator ArkinyStoica Alex Arkiny Data 27 martie 2015 23:01:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<fstream>
#include<string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

#define MAX 2000010

char str[MAX],sub_str[MAX];
int r[1000],nr,pref[MAX];

void prefix(int pref[],char sub_str[])
{
	int i=0,j=1,l=strlen(sub_str);
	
	while(j<l)
	{
		if(sub_str[j]==sub_str[i])
		{pref[j]=++i;++j;}
		else if(i>0)
			i=pref[i-1];
		else
			++j;
	}
}

void KMP(char str[],char sub_str[])
{
	int i=0,j=0,l1=strlen(str),l2=strlen(sub_str);
	prefix(pref,sub_str);
	while(i<l1)
	{
		if(j<l2)
		{
			if(str[i]==sub_str[j])
			 {++i;++j;}
			else if(j>0)
				j=pref[j-1];
			else
				++i;
		}
		if(j>=l2)
		{
			j=pref[j-1];
			if(nr<1000)
				r[nr]=i-l2;
			++nr;
		}
	}
}

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

	out<<nr<<'\n';

	for(int i=0;i<nr && i<1000;i++)
		out<<r[i]<<" ";

	in.close();
	out.close();
	return 0;
}