Cod sursa(job #791002)

Utilizator adascaluAlexandru Dascalu adascalu Data 22 septembrie 2012 18:09:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#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=0,nb=0,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;
	}
	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;
}