Cod sursa(job #1560258)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 2 ianuarie 2016 12:40:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<cstdio>
#include<cstring>
#include<vector> 
using namespace std;
const int NMAX = 2000005;
const int MOD1 = 100009;
const int MOD2 = 666013;
const int BASE = 107;
int i,N,M,Cnt,HashA1,HashA2,HashB1,HashB2,B1,B2;
char A[NMAX],B[NMAX];
vector<int> Sol;
vector<int>::iterator it;
int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s%s",A+1,B+1);
    N=strlen(A+1); M=strlen(B+1);
    B1=B2=1;
    for(i=1;i<=N;i++)
    {
        HashA1=(HashA1*BASE+A[i])%MOD1;
        HashA2=(HashA2*BASE+A[i])%MOD2;
        B1=(B1*BASE)%MOD1;
        B2=(B2*BASE)%MOD2;
    }
 
    for(i=1;i<=N;i++)
    {
        HashB1=(HashB1*BASE+B[i])%MOD1;
        HashB2=(HashB2*BASE+B[i])%MOD2;
    }
    if(HashB1==HashA1 && HashB2==HashA2)
    {
        Cnt++;
        if(Cnt<=1000) Sol.push_back(0);
    }
 
    for(i=N+1;i<=M;i++)
    {
        HashB1=(((HashB1*BASE)%MOD1-(B[i-N]*B1)%MOD1+MOD1)%MOD1+B[i])%MOD1;
        HashB2=(((HashB2*BASE)%MOD2-(B[i-N]*B2)%MOD2+MOD2)%MOD2+B[i])%MOD2;
        if(HashB1==HashA1 && HashB2==HashA2)
        {
            Cnt++;
            if(Cnt<=1000) Sol.push_back(i-N);
        }
    }
    printf("%d\n",Cnt);
    for(it=Sol.begin();it!=Sol.end();it++) printf("%d ",*it);
    return 0;
}