Cod sursa(job #2240915)

Utilizator greelioGreenio Greely greelio Data 14 septembrie 2018 14:39:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include<bits/stdc++.h>
#define int long long
#define NMAX 2000010
using namespace std;


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

const int MOD1 = 100007;
const int MOD2 = 100021;
const int P = 73;
string a,b;
int ha1,ha2, h1,h2, d1=1,d2=1, rs;
bool u[NMAX];

int32_t main() {
    fin>>a>>b;
    int sa = a.size(), sb=b.size();

    if (sa>sb) return fout<<0,0;

    for (int i=0; i<sa; i++) {
        ha1 = (ha1*P + a[i])%MOD1;
        ha2 = (ha2*P + a[i])%MOD2;
        h1 = (h1*P + b[i])%MOD1;
        h2 = (h2*P + b[i])%MOD2;
        if (i != 0) {
            d1 = (d1*P)%MOD1;
            d2 = (d2*P)%MOD2;
        }
    }
    if (h1==ha1 && h2==ha2) ++rs, u[0]=1;

    for (int i=sa; i<sb; i++) {
        h1 = ((h1 - (b[i - sa]*d1)%MOD1 + MOD1)*P + b[i])%MOD1;
        h2 = ((h2 - (b[i - sa]*d2)%MOD2 + MOD2)*P + b[i])%MOD2;
        if (h1 == ha1 && h2 == ha2) {
            rs++;
            u[i-sa+1]=1;
        }
    }
    fout<<rs<<'\n'; rs=1000;
    for (int i=0; i<sb && rs; i++) {
        if (u[i]) {
            fout<<i<<" "; rs--;
        }
    }

    return 0;
}