Cod sursa(job #694895)

Utilizator pandreeaePopescu Andreea pandreeae Data 28 februarie 2012 08:51:10
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <stdio.h>
using namespace std;

char t[2000005], p[2000005];
int n=0, m=0, q, k, i, u[1000]={0}, e=0, f[1001];

void prefixeaza ()
{
	u[1]=0;
	q=0;
	for(i=2;i<m;i++){
		while(q>0&&p[q+1]!=p[i])
			q=u[q];
		if(p[q+1]==p[i])
			++q;
		u[i]=q;}
}

void calc ()
{
	for(;(p[m]>='A'&&p[m]<='Z')||(p[m]>='a'&&p[m]<='z')||(p[m]>='0'&&p[m]<='9');++m);
	for(;(t[n]>='A'&&t[n]<='Z')||(t[n]>='a'&&t[n]<='z')||(t[n]>='0'&&t[n]<='9');++n);
	for(i=m;i;--i) 
		p[i]=p[i-1]; 
	p[0]=' ';
	for(i=n;i;--i) 
		t[i]=t[i-1]; 
	t[0]=' ';
}

int main ()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	fgets(p,sizeof(p),stdin);
	fgets(t,sizeof(t),stdin);
	calc();
	prefixeaza();
	q=0;
	for(i=1;i<=n;++i){
		while(q&&p[q+1]!=t[i])
			q=u[q];
		if(p[q+1]==t[i])
			++q;
		if(q==m){
			++e;
			if(e<=1000)
				f[e]=i-m;
			q=u[q];}}
	printf("%d\n",e);
	for(i=1;i<=e&&i<=1000;i++)
		printf("%d ",f[i]);
	return 0;
}