Cod sursa(job #2977185)

Utilizator biancalautaruBianca Lautaru biancalautaru Data 11 februarie 2023 00:14:01
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <fstream>
#include <cstring>
#define DIM 2000005
#define mod 739379
#define mod1 119797
#define baza 26
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long n,m,p,p1,h1,hh1,h2,hh2,cnt,sol[DIM];
char a[DIM],b[DIM];
int main() {
    fin>>a>>b;
    n=strlen(a);
    m=strlen(b);
    if (n>m) {
        fout<<0;
        return 0;
    }
    p=p1=1;
    for (int i=0;i<n;i++) {
        h1=(h1*baza+a[i])%mod;
        hh1=(hh1*baza+a[i])%mod1;
        h2=(h2*baza+b[i])%mod;
        hh2=(hh2*baza+b[i])%mod;
        if (i!=0) {
            p=p*baza%mod;
            p1=p1*baza%mod1;
        }
    }
    if (h1==h2 && hh1==hh2)
        sol[++cnt]=0;
    for (int i=n;i<m;i++) {
        h2=((h2-(b[i-n]*p)%mod+mod)*baza+b[i])%mod;
        hh2=((hh2-(b[i-n]*p1)%mod1+mod1)*baza+b[i])%mod1;
        if (h1==h2 && hh1==hh2)
            sol[++cnt]=i-n+1;
    }
    fout<<cnt<<"\n";
    for (int i=1;i<=cnt && i<=1000;i++)
        fout<<sol[i]<<" ";
    return 0;
}