Cod sursa(job #1294911)

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

int prefix[2000000];
char s[2000000];
char subs[2000000];
int val[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]=0;
    int a=0;

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

	}


}

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

	int i=0,j=0;

	for(int i=0;i<N;i++)
	{
		if(s[i]==subs[j])
		{
			j++;
			if(j==M)
			{
				   if(nr<1000)
				      val[nr]=i-M+1l;
                    ++nr;
				   j=prefix[j-1];
			}
		}
		else if(j > 0 && s[i]!=subs[j])
		{
			j=prefix[j-1];

			if(j>0)
				i--;

		}
	}


}

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

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

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

	return 0;

}