Cod sursa(job #1428841)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 5 mai 2015 10:25:19
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>

using namespace std;

const int BASE = 137;

template <const int MOD>
class RollingHash
{
public:

    int length;
    int code;
    int base;

    RollingHash(const int lg = 0) : length(lg), code(0), base(1) {

        for (int i = 1; i < lg; ++i)
            base = (1LL * base * BASE) % MOD;
    }

    void pop_front(const char ch)
    {
        code = (code -  (base * ch) % MOD + MOD) % MOD;
    }

    void push_back(const char ch)
    {
        code = (code * BASE) % MOD;
        code = (code + ch) % MOD;
    }
};

const int Nmax = 2000000;

char A[Nmax], B[Nmax];
int N, M;

int main()
{
    ifstream in("strmatch.in");
    ofstream out("strmatch.out");

    in >> A >> B;
    N = strlen(A);
    M = strlen(B);

    RollingHash<666013> A1(N);
    RollingHash<1000000007> A2(N);
    RollingHash<666013> B1(N);
    RollingHash<1000000007> B2(N);

    if (N > M)
    {
        cout << "0\n";
        return 0;
    }

    for (int i = 0; i < N; ++i)
    {
        A1.push_back(A[i]);
        A2.push_back(A[i]);

        B1.push_back(B[i]);
        B2.push_back(B[i]);
    }

    vector<int> sol;

    if (A1.code == B1.code && A2.code == B2.code)
        sol.push_back(0);

    for (int i = N; i < M; ++i)
    {
        B1.pop_front(B[i - N]);
        B2.pop_front(B[i - N]);

        B1.push_back(B[i]);
        B2.push_back(B[i]);

        if (A1.code == B1.code && A2.code == B2.code)
            sol.push_back(i - N + 1);
    }

    out << sol.size() << "\n";

    for (int i = 0; i < min(1000, (int)sol.size()); ++i)
        out << sol[i] << " ";

    out << "\n";

    return 0;
}