Cod sursa(job #2789477)

Utilizator IoanMihaiIoan Mihai IoanMihai Data 27 octombrie 2021 16:20:45
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define MOD1 100007
#define MOD2 100021
#define P 73
long long n, m, h, hp, p1, p2, h1, h2;
int v[2000005];
char a[2000005], b[2000005];
int main() {
    fin >> a >> b;

    n = strlen(a);
    m = strlen(b);

    p1 = p2 = 1;
    for (int i=0;i<n;i++){
        h = (h * P + a[i]) % MOD1;
        hp = (hp * P + a[i]) % MOD2;

        if (i != 0){
            p1 = (p1 * P) % MOD1;
            p2 = (p2 * P) % MOD2;
        }
    }

    if (n > m){
        fout << "0\n";
        return 0;
    }

    for (int i=0;i<n;i++){
        h1 = (h1 * P + b[i]) % MOD1;
        h2 = (h2 * P + b[i]) % MOD2;
    }

    int ans = 0;
    if (h1 == h && h2 == hp){
        v[0] = 1;
        ans ++;
    }

    for (int i=n;i<m;i++){
        h1 = ((h1 - (b[i-n] * p1) % MOD1 + MOD1) * P + b[i]) % MOD1;
        h2 = ((h2 - (b[i-n] * p1) % MOD2 + MOD2) * P + b[i]) % MOD2;

        if (h1 == h && h2 == hp)
            v[i - n + 1] = 1, ans ++;
    }

    fout << ans << '\n';

    ans = 0;
    for (int i=0;i<m && ans < 1000;i++)
        if (v[i])
            ans ++, fout << i << ' ';
    fout << '\n';
    return 0;
}