Cod sursa(job #2240907)

Utilizator DimaTCDima Trubca DimaTC Data 14 septembrie 2018 14:17:21
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.88 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 m = 100000000091;
const int p = 103;
string a,b;
int ha, h1, d=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++) {
        ha = (ha*p + a[i])%m;
        h1 = (h1*p + b[i])%m;

        if (i != 0) {
            d = (d*p)%m;
        }
    }
    if (h1==ha) ++rs, u[0]=1;

    for (int i=sa; i<sb; i++) {
        h1 = ((((h1 - (b[i - sa]*d)%m + m)%m)*p) + b[i])%m;
        if (h1 == ha) {
            rs++;
            u[i-sa+1]=1;
        }
    }
    fout<<rs<<'\n';
    for (int i=0; i<sb && rs; i++) {
        if (u[i]) {
            fout<<i<<" "; rs--;
        }
    }

    return 0;
}