Cod sursa(job #2338503)

Utilizator DovlecelBostan Andrei Dovlecel Data 7 februarie 2019 15:57:13
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <fstream>
#include <string.h>

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N=2000001;
const int p=73;
const int MOD1=100007;
const int MOD2=100021;
char A[N],B[N];
int na,nb,p1=1,p2=1,hashA1,hashA2,cnt;
bool match[N];

int main()
{
    in>>A;
    in>>B;
    na=strlen(A);
    nb=strlen(B);
    hashA1=hashA2=A[0];
    int hash1,hash2;
    hash1=hash2=B[0];
    for(int i=1;i<na;i++)
    {
        hashA1=(hashA1*p+A[i])%MOD1;
        hashA2=(hashA2*p+A[i])%MOD2;
        hash1=(hash1*p+B[i])%MOD1;
        hash2=(hash2*p+B[i])%MOD2;
        p1=(p*p1)%MOD1;
        p2=(p*p2)%MOD2;
    }
    if(na>nb)
    {
        out<<0;
        return 0;
    }
    for(int i=na;i<=nb;i++)
    {
        if(hash1==hashA1 && hash2==hashA2)
        {
            cnt++;
            match[i-na]=true;
        }
        hash1=((hash1-(p1*B[i-na])%MOD1+MOD1)*p+B[i])%MOD1;
        hash2=((hash2-(p2*B[i-na])%MOD2+MOD2)*p+B[i])%MOD2;
    }
    out<<cnt<<'\n';
    for(int i=0;i<nb-na+1;i++)
        if(match[i])
            out<<i<<' ';
    return 0;
}