Cod sursa(job #812937)

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

#define maxn 2000005
#define X 71
#define mod1 100007
#define mod2 100021
#define maxsol 1001

char a[maxn], b[maxn];
int lena, lenb ;
int hasha1, hasha2 ;
int hashb1, hashb2 ;
int sol[maxsol] ;

int main()
{
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	scanf("%s\n", a + 1);
	lena = strlen(a + 1);
	
	scanf("%s\n", b + 1);
	lenb = strlen(b + 1);
	
	int X1 = 1 ;
	int X2 = 1 ;
	
	for(int i = 1; i <= lena; ++i )
	{
		hasha1 = (hasha1 * X + a[i] ) % mod1 ;
		hasha2 = (hasha2 * X + a[i] ) % mod2 ;
		
		X1 = ( X1 * X ) % mod1 ;
		X2 = ( X2 * X ) % mod2 ;
	}

	for(int i = 1; i <= lena; ++i )
	{
		hashb1 = ( hashb1 * X + b[i] ) % mod1 ;
		hashb2 = ( hashb2 * X + b[i] ) % mod2 ;
	}
	
	if( hashb1 == hasha1 && hashb2 == hasha2 )
		sol[ ++sol[0] ] = 0 ;
	
	for(int i = lena + 1; i <= lenb; ++i )
	{
		hashb1 = ( hashb1 * X + b[i] ) % mod1 ;
		hashb2 = ( hashb2 * X + b[i] ) % mod2 ;
		
		hashb1 = ( hashb1 - ( b[i-lena] * X1 ) % mod1 + mod1 ) % mod1 ;
		hashb2 = ( hashb2 - ( b[i-lena] * X2 ) % mod2 + mod2 ) % mod2 ;
		
		if( hashb1 == hasha1 && hashb2 == hasha2 )
		{
			++sol[0] ;
			if( sol[0] > 1000 )
				continue ;
			sol[ sol[0] ] = i - lena ;
		}
	}
	
	printf("%d\n", sol[0]);
	
	for(int i = 1; i <= min(1000, sol[0]); ++i )
		printf("%d ", sol[i]);
	
	printf("\n");
	
	return 0 ;
	
}