Cod sursa(job #384790)

Utilizator iulia609fara nume iulia609 Data 20 ianuarie 2010 22:47:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<stdio.h>
#include<string>
using namespace std;
#define NMAX 1<<21
int N, M, k;

int A[1<<10], P[NMAX];
char V[NMAX], W[NMAX];

void pref()
{ int i, q;

	q = 0; P[1] = 0;
	
	for(i = 2; i <= N; i++)
	{
		while(q != 0 && V[q+1] != V[i])
			q = P[q];
		
		if(V[q+1] == V[i])
			q++;
		
		P[i] = q;
	}
}

void solve()
{ int i, q;

	q = N+1;
	for(i = 1; i <= M; i++)
	{
		while(q != 0 && V[q+1] != W[i])
			q = P[q];
		
		if(V[q+1] == W[i])
			q++;
		
		if(q == N)
		{
			q = P[q];
			k++;
			
			A[k] = (k <= 1000) ? i-N : 0;
		}
	}
}

int main()
{ int i;

	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	gets(V+1);
	N = strlen(V+1);
	
	gets(W+1);
	M = strlen(W+1);
	
	pref();
	solve();
	
	printf("%d\n", k);
	
	k = (k < 1000) ? k : 1000;
	
	for(i = 1; i <= k; i++)
		printf("%d ", A[i]);
	
	return 0;
}