Cod sursa(job #1075726)

Utilizator Lucian-GeorgeFMI Popa Lucian George Lucian-George Data 9 ianuarie 2014 15:14:58
Problema Potrivirea sirurilor Scor 52
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 kb
#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;

int pref[2000005];
char A[2000005],B[2000005];
int main()
{
	int i,j,poz,ok,p,l,nr=0,t[1024];
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");
	f>>A>>B;
	
	l=strlen(A);
	
	int k=0;
	pref[1]=0;
	for (i=2; i<=l; i++)
	{
		while (k>0 && A[k]!=A[i-1]) k=pref[k];
		if (A[k]==A[i-1]) k=k+1;
		pref[i]=k;
	}

	
    //for (i = 1; i <l; ++i)
    //{
    //    if (A[i]==A[pref[i-1]]) pref[i]=pref[i-1]+1;
	//	else if (A[i]==A[0]) pref[i]=1;
	//	else pref[i]=0;
   // }

	
	int q=strlen(B);
	
	for (i=1; i<=q; i++)
	{
		while (k>0 && A[k]!=B[i-1]) k=pref[k];
		if (A[k]==B[i-1]) k=k+1;
		if (k==l)
		{
			nr++;
			if (nr<=1000) t[nr]=i-l;
		}
	}
	
	g<<nr<<"\n";
	
	if (nr<1000) for (i=1; i<=nr; i++) g<<t[i]<<" ";
	else for (i=1; i<=1000; i++) g<<t[i]<<" ";
	
	return 0;
}