Cod sursa(job #2008260)

Utilizator savigunFeleaga Dragos-George savigun Data 5 august 2017 22:01:43
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 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 = 3, C2 = 5;
int n, m;
char a[2000002], b[2000002];
ULL ha, ha2, hb[2000001], hb2[2000001];
int sol[1001];


inline ULL pow(ULL a, int n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return pow(a * a, n / 2);
    return a * pow(a, n - 1);
}

inline void preprocess() {
    for (int i = n; i >= 0; --i) {
        hb[i] = b[i] + hb[i + 1] * C;
        hb2[i] = b[i] + hb2[i + 1] * C2;
        if (i < m) {
            ha += a[i] * pow(C, i);
            ha2 += a[i] * pow(C2, i);
        }
    }
}


inline ULL get_hash(int l, int r) {
    return hb[l] - hb[r + 1] * pow(C, r - l + 1);
}

inline ULL get_hash2(int l, int r) {
    return hb2[l] - hb2[r + 1] * pow(C2, r - l + 1);
}


int main()
{

    in >> a;
    in >> b;

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

    preprocess();


    int stop = n - m + 1;
    for (int i = 0; i <= stop; ++i) {
        ULL h = get_hash(i, i + m - 1);
        ULL h2 = get_hash2(i, i + m - 1);
        if (h == ha && h2 == ha2) {
            sol[0]++;
            if (sol[0] <= 1000) sol[sol[0]] = i;
        }
    }


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

    return 0;
}