Cod sursa(job #408817)

Utilizator lalasCont de teste lalas Data 3 martie 2010 11:31:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 2000005;

int i , j , k , n , m , q;
char A[maxn] , B[maxn];
int rez[1010] , pi[maxn];

void 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()
{
	freopen("strmatch.in","r",stdin);
	freopen("strmatch.out","w",stdout);
	
	fgets(A,maxn,stdin);
	fgets(B,maxn,stdin);
	
	m = strlen(A) - 1;
	n = strlen(B) - 1;
	
	for ( i = m ; i >= 1 ; --i ) A[i] = A[i - 1];
	for( i = n ; i >= 1 ; --i ) B[i] = B[i - 1];
	
	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];
			k++;
			if ( k <= 1000 ) rez[k] = i - m;
		}
	}
	
	printf("%d\n",k);
	for( i = 1 ; i <=min(k,1000) ; ++i )
			printf("%d ",rez[i]);
	
return 0;	
}