Cod sursa(job #902718)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 1 martie 2013 16:23:52
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 4.89 kb
#include <cstdio>
#include <cstring>
#include <cassert>

#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>

using namespace std;

typedef long long LL;
typedef vector<int>::iterator it;

const int oo = 0x3f3f3f3f;
const int MAX_N = 2000005;
const int MAX_MATCH = 1000;
const int MAX_U = 2;
const int U[] = {666013, 1000000007};
const int Base = 61;

struct Key {
    int Values[MAX_U];

    Key() {
        memset(Values, 0, sizeof(Values));
    }

    Key(const LL X) {
        for (int i = 0; i < MAX_U; ++i)
            Values[i] = X % U[i];
    }

    Key operator= (const Key &Other) {
        memcpy(Values, Other.Values, sizeof(Other.Values));
        return *this;
    }

    Key operator= (const LL X) {
        *this = Key(X);
        return *this;
    }

    Key operator+ (const Key &Other) const {
        Key Result;
        for (int i = 0; i < MAX_U; ++i)
            Result.Values[i] = (Values[i] + Other.Values[i] + U[i]) % U[i];
        return Result;
    }

    Key operator- (const Key &Other) const {
        Key Result;
        for (int i = 0; i < MAX_U; ++i)
            Result.Values[i] = (Values[i] - Other.Values[i] + U[i]) % U[i];
        return Result;
    }

    Key operator* (const Key &Other) const {
        Key Result;
        for (int i = 0; i < MAX_U; ++i)
            Result.Values[i] = (1LL * Values[i] * Other.Values[i]) % U[i];
        return Result;
    }

    Key operator+ (const LL X) const {
        return *this + Key(X);
    }

    Key operator- (const LL X) const {
        return *this - Key(X);
    }

    Key operator* (const LL X) const {
        return *this * Key(X);
    }

    bool operator== (const Key &Other) const {
        for (int i = 0; i < MAX_U; ++i)
            if (Values[i] != Other.Values[i])
                return false;
        return true;
    }
};

int N, M, MatchCount;
char Pattern[MAX_N], String[MAX_N];
vector<int> MatchPositions;
/*
int Pi[MAX_N];
int Z[MAX_N];

void BuildPi() {
    Pi[1] = 0;
    for (int i = 1, p = 0; i < N; ++i) {
        for (; p > 0 && Pattern[i + 1] != Pattern[p + 1]; p = Pi[p]);
        p += (Pattern[i + 1] == Pattern[p + 1] ? 1 : 0);
        Pi[i + 1] = p;
    }
}

void KMP() {
    BuildPi();
    for (int i = 1, p = 0; i <= M; ++i) {
        for (; p > 0 && String[i] != Pattern[p + 1]; p = Pi[p]);
        p += (String[i] == Pattern[p + 1] ? 1 : 0);
        if (p == N) {
            ++MatchCount;
            if (MatchCount <= MAX_MATCH)
                MatchPositions.push_back(i - N + 1);
        }
    }
}

void BuildZ() {
    int Right = 0, Position = 0;
    for (int i = 2; i <= N; ++i) {
        if (Right >= i)
            Z[i] = min(Right - i + 1, Z[i - Position + 1]);
        for (; i + Z[i] <= N && Pattern[Z[i] + 1] == Pattern[i + Z[i]]; ++Z[i]);
        if (i + Z[i] - 1 > Right) {
            Position = i;
            Right = i + Z[i] - 1;
        }
    }
}

void ZAlgorithm() {
    BuildZ();
    int Right = 0, Position = 0;
    for (int i = 1; i <= M; ++i) {
        int LCP = 0;
        if (Right >= i)
            LCP = min(Right - i + 1, Z[i - Position + 1]);
        for (; LCP < N && i + LCP <= M && Pattern[LCP + 1] == String[i + LCP]; ++LCP);
        if (i + LCP - 1 > Right) {
            Position = i;
            Right = i + LCP - 1;
        }
        if (LCP == N) {
            ++MatchCount;
            if (MatchCount <= MAX_MATCH)
                MatchPositions.push_back(i);
        }
    }
}*/

inline int Digit(const char C) {
    if ('a' <= C && C <= 'z')
        return C - 'a' + 1;
    if ('A' <= C && C <= 'Z')
        return C - 'A' + 27;
    return 0;
}

void RabinKarp() {
    Key PatternHash = 0, BasePow = 1;
    for (int i = 1; i <= N; ++i) {
        PatternHash = (PatternHash * Base + Digit(Pattern[i]));
        BasePow = BasePow * Base;
    }
    Key Hash = 0;
    for (int i = 1; i < N; ++i)
        Hash = Hash * Base + Digit(String[i]);
    for (int i = N; i <= M; ++i) {
        Hash = Hash * Base + Digit(String[i]);
        Hash = Hash - BasePow * Digit(String[i - N]);
        if (Hash == PatternHash) {
            ++MatchCount;
            if (MatchCount <= MAX_MATCH)
                MatchPositions.push_back(i - N + 1);
        }
    }
}

void Solve() {
    //KMP();
    //ZAlgorithm();
    RabinKarp();
}

void Read() {
    assert(freopen("strmatch.in", "r", stdin));
    assert(scanf("%s\n%s", Pattern + 1, String + 1) == 2);
    N = strlen(Pattern + 1);
    M = strlen(String + 1);
}

void Print() {
    assert(freopen("strmatch.out", "w", stdout));
    printf("%d\n", MatchCount);
    for (it P = MatchPositions.begin(); P != MatchPositions.end(); ++P)
        printf("%d ", *P - 1);
    printf("\n");
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}