Cod sursa(job #1403681)

Utilizator ArkinyStoica Alex Arkiny Data 27 martie 2015 15:11:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

char s1[2000000],s2[2000000];
int prefix[2000000];
int rez[1000];
ifstream in("strmatch.in");
ofstream out("strmatch.out");
int nr=0;
void pref(int prefix[],char s2[])
{
	int a=0;
	int j=1;
	prefix[0]=a;
	int l=strlen(s2);
	while(j<l)
	{
		if(s2[j]==s2[a])
		{
			 prefix[j]=prefix[j-1]+1;
			++a;
			++j;
		}
		else if(a>0)
		{
			a=prefix[a-1];
		}
		else ++j;
	}
}
void KMP(char s1[],char s2[])
{
	pref(prefix,s2);
	int i=0,j=0,l1=strlen(s1),l2=strlen(s2);
	while(i<l1)
	{
		if(j<l2)
		{
			if(s1[i]==s2[j])
			{
				++j;
				++i;
			}
			else if(j>0)
			{
				j=prefix[j-1];
			}
			else
				++i;
		}
		if(j>=l2)
		{
			j=prefix[j-1];
			if(nr<1000)
			  rez[nr++]=i-l2;
		}
	}
}
int main()
{

	in>>s2;
	in>>s1;
	KMP(s1,s2);
	out<<nr<<endl;
	for(int i=0;i<nr && i<1000;i++)
		out<<rez[i]<<" ";
	in.close();
	out.close();
	return 0;
}