Cod sursa(job #2008266)

Utilizator savigunFeleaga Dragos-George savigun Data 5 august 2017 22:48:30
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

typedef unsigned int ULL;

const int C = 2, C2 = 3;
int n, m;
char a[2000002], b[2000002];
ULL ha, ha2, hb, hb2, powC, powC2;
int sol[1001];

inline void preprocess() {
    powC = 1;
    powC2 = 1;

    for (int i = 0; i <= m; ++i) {
        ha += a[i] * powC;
        ha2 += a[i] * powC2;
        hb += b[i] * powC;
        hb2 += b[i] * powC2;
        if (i < m) {
            powC *= C;
            powC2 *= C2;
        }
    }

}

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

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

    preprocess();

    for (int i = 0; i <= n - m; ++i) {
        if (ha == hb && ha2 == hb2) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
        if (i + m + 1 > n) continue;
        hb -= b[i];
        hb /= C;
        hb += b[i + m + 1] * powC;
        hb2 -= b[i];
        hb2 /= C2;
        hb2 += b[i + m + 1] * powC2;
    }


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

    return 0;
}