Cod sursa(job #1458818)

Utilizator ArkinyStoica Alex Arkiny Data 8 iulie 2015 15:28:46
Problema Potrivirea sirurilor Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include<iostream>
#include<string.h>
#include<fstream>
using namespace std;

#define MAX 2000001

int P[MAX],n;
char str[MAX],sub_str[MAX];
int d[1001];
ifstream in("strmatch.in");
ofstream out("strmatch.out");

void make_prefix(int l)
{
	int i=1,j=0;
	while(i<l)
	{
		while(i<l && sub_str[i] == sub_str[j])
		{
			P[i]=P[i-1]+1;
			++j;
			++i;
		}

		if(j>0 && i<l)
		{
			j=P[i-1];
			while(j>0 && sub_str[j]!=sub_str[i])
				j=P[j-1];

			if(j>0)
				P[i]=P[j]+1;
			else if(sub_str[i] == sub_str[j])
					P[i]=P[j]+1;
			
			++j;
			++i;
		}
		else
			++i;
	}

}

void KMP()
{
	int l_str=strlen(str),l_substr=strlen(sub_str);

	make_prefix(l_substr);


	int i=0,j=0;
    
	while(i<l_str)
	{
		while(j<l_substr && i<l_str && sub_str[j] == str[i] )
			   ++i,++j;
		if(j>=l_substr)
		{
				++n;
				if(n<=1000)
				{
					d[n]=i-j;
				}
		}
		if(j>0 && i<l_str)
		{
			j=P[j-1];
			while(j>0 && sub_str[j] != str[i])
				j=P[j-1];
		}
		else
			++i;

	}
}

int main()
{

	in>>sub_str>>str;
	KMP();
	out<<n<<'\n';
	for(int i=1;i<=1000 && i<=n;i++)
		out<<d[i]<<" ";

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

	return 0;
}