Cod sursa(job #2008280)

Utilizator savigunFeleaga Dragos-George savigun Data 6 august 2017 01:08:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

typedef unsigned int UI;

const int MAXN = 2000005;
const UI MOD1 = 100007;
const UI MOD2 = 100009;
const UI B = 73;
char a[MAXN], b[MAXN];
UI ha, ha2, hb, hb2, p1, p2;
int n, m;
int sol[1001];


inline void preprocess() {
    p1 = 1;
    p2 = 1;

    for (int i = 0; i <= m; ++i) {
        if (i != 0) {
            p1 = (p1 * B) % MOD1;
            p2 = (p2 * B) % MOD2;
        }
        ha = (ha * B + a[i]) % MOD1;
        ha2 = (ha2 * B + a[i]) % MOD2;
        hb = (hb * B + b[i]) % MOD1;
        hb2 = (hb2 * B + b[i]) % MOD2;
    }
}

int main()
{
    in >> a;
    in >> b;

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

    preprocess();

    for (int i = 0; i <= n - m; ++i) {
        if (i != 0) {
            hb = ((hb - (b[i - 1] * p1) % MOD1 + MOD1) * B + b[i + m]) % MOD1;
            hb2 = ((hb2 - (b[i - 1] * p2) % MOD2 + MOD2) * B + b[i + m]) % MOD2;
        }
        if (ha == hb && ha2 == hb2) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
    }

    out << sol[0] << "\n";
    int stop = min(sol[0], 1000);
    for (int i = 1; i <= stop; ++i) {
        out << sol[i] << " ";
    }

    return 0;
}