Cod sursa(job #1414556)

Utilizator matei_cChristescu Matei matei_c Data 2 aprilie 2015 19:04:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<cmath>
#include<climits>
using namespace std ;

#define maxn 2000005
#define maxp 1005

#define X 101
#define MOD1 100003
#define MOD2 100007
#define MOD3 100005

char a[maxn], b[maxn] ;

int X1 = 1, X2 = 1, X3 = 1, hasha1, hasha2, hashb1, hashb2, hasha3, hashb3 ;

int sol[maxp] ;

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

    scanf("%s\n", a + 1);
    int na = strlen(a + 1) ;

    scanf("%s\n", b + 1);
    int nb = strlen(b + 1) ;

    for(int i = 1; i <= na; ++i)
    {
        hasha1 = ( hasha1 * X + a[i] ) % MOD1 ;
        hasha2 = ( hasha2 * X + a[i] ) % MOD2 ;
        hasha3 = ( hasha3 * X + a[i] ) % MOD3 ;

        hashb1 = ( hashb1 * X + b[i] ) % MOD1 ;
        hashb2 = ( hashb2 * X + b[i] ) % MOD2 ;
        hashb3 = ( hashb3 * X + b[i] ) % MOD3 ;

        X1 = ( X1 * X ) % MOD1 ;
        X2 = ( X2 * X ) % MOD2 ;
        X3 = ( X3 * X ) % MOD3 ;
    }

    if( hasha1 == hashb1 && hasha2 == hashb2 )
        sol[ ++sol[0] ] = 0 ;

    for(int i = na + 1; i <= nb; ++i)
    {
        hashb1 = ( hashb1 * X + b[i] ) % MOD1 ;
        hashb1 = ( hashb1 - ( b[i - na] * X1 ) % MOD1 + MOD1 ) % MOD1 ;

        hashb2 = ( hashb2 * X + b[i] ) % MOD2 ;
        hashb2 = ( hashb2 - ( b[i - na] * X2 ) % MOD2 + MOD2 ) % MOD2 ;

        hashb3 = ( hashb3 * X + b[i] ) % MOD3 ;
        hashb3 = ( hashb3 - ( b[i - na] * X3 ) % MOD3 + MOD3 ) % MOD3 ;

        if( hasha1 == hashb1 && hasha2 == hashb2 && hasha3 == hashb3 )
        {
            ++sol[0] ;

            if( sol[0] > 1000 )
                continue ;

            sol[ sol[0] ] = i - na ;
        }
    }

    printf("%d\n", sol[0]);

    for(int i = 1; i <= min( sol[0], 1000 ); ++i )
        printf("%d ", sol[i]);

	return 0 ;
}