Cod sursa(job #1671812)

Utilizator feli2felicia iuga feli2 Data 2 aprilie 2016 10:54:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int MOD=666013, b=80, Max=2000005;
int rez[1005], hashA, hashB, nr;
char A[Max], B[Max];

int main()
{
    fin>>A>>B;
    int na=strlen(A);
    int nb=strlen(B);
    if(na>nb)
    {
        fout<<0;
        return 0;
    }
    int p=1;
    for(int i=0;i<na;i++)
    {
        int c=A[i]-'0'+1;
        hashA=((hashA*b)%MOD+c)%MOD;
        if(i!=0)
        {
            p*=b;
            p%=MOD;
        }
    }
    for(int i=0;i<na;i++)
    {
        int c=B[i]-'0'+1;
        hashB=((hashB*b)%MOD+c)%MOD;
    }
    if(hashA==hashB)
    {
        nr++;
        rez[nr]=0;
    }
    for(int i=na;i<nb;i++)
    {
        int c1=B[i-na]-'0'+1;
        int c2=B[i]-'0'+1;
        hashB=((hashB-(p*c1)%MOD+MOD)*b+c2)%MOD;
        if(hashA==hashB)
        {
            int j;
            for(j=0;j<na;j++)
            {
                if(A[j]!=B[i-na+1+j])
                {
                    break;
                }
            }
            if(j>=na)
            {
                nr++;
                if(nr<=1000)
                    rez[nr]=i-na+1;
            }
        }
    }
    fout<<nr<<'\n';
    for(int i=1;i<=min(nr,1000);i++)
    {
        fout<<rez[i]<<" ";
    }
    return 0;
}