Cod sursa(job #694046)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 27 februarie 2012 18:17:34
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include<fstream>
#include<string.h>
using namespace std;
int urm[2000002],n,m,i,x=-1,c[2000002],q;
char a[2000002],b[2000002];
void urmatorul()
{
	int k=-1 ,x;
	urm[0]=0;
	for(x=1;x<m;x++)
	{
		while(k>0 && b[k+1]!=b[x])k=urm[k];
		if(b[k+1]==b[x])k++;
		urm[x]=k;
	}
}
int main()//cauta pe b in a
{
	ifstream f("strmatch.in");ofstream g("strmatch.out");
	f.getline(b,1000); m=strlen(b);
	f.getline(a,1000); n=strlen(a);
	urmatorul();
	for(i=0;i<n;i++)
	{
		while(x>0 && b[x+1]!=a[i]) x=urm[x];
		if(b[x+1]==a[i])x++;
		if(x==m-1)
		{
			c[++q]=i-m+1;
			x=urm[x];
		}
	}
	g<<q<<'\n';
	for(i=1;i<=q;i++) g<<c[i]<<' ';
	f.close();g.close();
return 0;}