Cod sursa(job #706119)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 5 martie 2012 17:08:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
#define minim(a, b) ((a < b) ? a : b)
#define NMax 2000005
int M, N;
char A[NMax], B[NMax];
int pi[NMax];
vector<int>v;
void make_prefix()
{
	int i,q=0;

	for (i=2,pi[1]=0;i<=M;++i)
	{
		while(q&&A[q+1]!=A[i])
			q=pi[q];
		if(A[q+1]==A[i])
			++q;
		pi[i]=q;
	}
}
int main()
{
	int i,q=0;
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	scanf("%s%s", &A, &B);
	M=strlen(A);
	N=strlen(B);
	for(i=M;i;--i) 
		A[i]=A[i-1]; 
	A[0]=' ';
	for(i=N;i;--i)
		B[i]=B[i-1];
	B[0] = ' ';		
	make_prefix();
	for(i=1;i<=N;++i)
	{		
		while(q&&A[q+1]!=B[i])
			q=pi[q];
		if(A[q+1]==B[i])
			++q;
		if(q==M)
		{
			q=pi[M];
			v.push_back((i-M));
		}	
	}		
	printf("%d\n", v.size());
	for(i=0;i<minim(v.size(),1000);++i)
		printf("%d ", v[i]);
	printf("\n");
	return 0;
}