Cod sursa(job #783792)

Utilizator adascaluAlexandru Dascalu adascalu Data 4 septembrie 2012 00:28:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include<cstdio>
#include<queue>
#include<vector>
#define P 699997
#define MAXN 2000001
using namespace std;
typedef unsigned int nat;
char a[MAXN],b[MAXN];
vector<nat>pi(MAXN);
queue<nat> rez;
int main()
{
	FILE *f=fopen("strmatch.in","r");
	FILE *g=fopen("strmatch.out","w");
	nat na,nb,i,k=0,n=0;
	char aux1,aux2;
	fscanf(f,"%s",a);
	fscanf(f,"%s",b);
	
	na=strlen(a);
	nb=strlen(b);
	aux1=a[0];
	for(i=1;i<=na;++i)
	{
		aux2=a[i];
		a[i]=aux1;
		aux1=aux2;
	}
	aux1=b[0];
	for(i=1;i<=nb;++i)
	{
		aux2=b[i];
		b[i]=aux1;
		aux1=aux2;
	}
	
	/*while(fscanf(f,"%c",aux1))
		a[++na]=aux1;
	while(fscanf(f,"%c",aux1))
		b[++nb]=aux1;*/
	pi[1]=0;
	for(i=2;i<=na;i++)
	{
		while(k && a[i]!=a[k+1])
			k=pi[k];
		if(a[i]==a[k+1])
			++k;
		pi[i]=k;
	}
	k=0;
	for(i=1;i<=nb;i++)
	{
		while(k && b[i]!=a[k+1])
			k=pi[k];
		if(b[i]==a[k+1])
			++k;
		if(k==na)
		{
			++n;
			if(n<1000)
				rez.push(i-na);
		}
	}
	fprintf(g,"%u\n",n);
	while(!rez.empty())
		fprintf(g,"%u ",rez.front()),rez.pop();
	fclose(f);
	fclose(g);
	return 0;
}