Cod sursa(job #812917)

Utilizator matei_cChristescu Matei matei_c Data 14 noiembrie 2012 18:04:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std ;

#define maxn 2000001
#define X 26
#define mod1 666013
#define mod2 666019

char a[maxn], b[maxn] ;
int hasha1, hasha2 ;
int hash1, hash2 ;
bool ok[maxn] ;

int main()
{
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s%s", a, b);
	
	int lena = strlen( a ) ;
	int lenb = strlen( b ) ;
	
	if( lena > lenb )
	{
		printf("0\n") ;
		return 0 ;
	}	
	
	int X1 = 1 ;
	int X2 = 1 ;
	
	for(int i = 0; i < lena; ++i )
	{
		hasha1 = ( hasha1 * X + a[i] ) % mod1 ;
		hasha2 = ( hasha2 * X + a[i] ) % mod2 ;
		
		if( i > 0 )
		{
			X1 = ( X1 * X ) % mod1 ;
			X2 = ( X2 * X ) % mod2 ;
		}	
		
		hash1 = (hash1 * X + b[i]) % mod1 ;
		hash2 = (hash2 * X + b[i]) % mod2 ;		
		
	}
	
	int nr = 0 ;
	
	if( hash1 == hasha1 && hash2 == hasha2)
	{
		ok[0] = true ;
		++nr ;
	}	
	
	for(int i = lena; i < lenb; ++i )
	{
		hash1 = ( ( hash1 - ( b[i-lena] * X1 ) % mod1 ) * X + b[i] ) % mod1 ;
		hash2 = ( ( hash2 - ( b[i-lena] * X2 ) % mod2 ) * X + b[i] ) % mod2 ;

		if( hash1 == hasha1 && hash2 == hasha2 )
		{
			ok[ i - lena + 1 ] = true ;
			++nr ;
		}	
	}
		
	printf("%d\n", nr) ;

	int cate = 0 ;
	
	for(int i = 0; i < lenb; ++i )
	{
		if( cate > 1000 )
			break ;
		if( ok[i] == true )
		{	
			++ cate ;
			printf("%d ", i);
		}
	}	
	
	printf("\n");
	
	return 0 ;

}