Cod sursa(job #2240918)

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


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() {
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);
    scanf("%s %s", a, b);
    int sa = a.size(), sb=b.size();

    if (sa>sb) return cout<<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;
        }
    }
    cout<<rs<<'\n'; rs=1000;
    for (int i=0; i<sb && rs; i++) {
        if (u[i]) {
            printf("%d ", i); rs--;
        }
    }

    return 0;
}