Cod sursa(job #1580945)

Utilizator andrei.arnautuAndi Arnautu andrei.arnautu Data 26 ianuarie 2016 12:40:54
Problema Potrivirea sirurilor Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
/**
  *  Worg
  */
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);

const int MAX_LEN = 1 + 2000000;
const long long P1 = 1000000007;
const long long P2 = 1000000009;

const long long BASE = 59;

unsigned long long pow(unsigned long long base, unsigned long long exp, unsigned long long P) {

    unsigned long long answer = 1, aux = base;
    for(unsigned long long i = 1; i <= exp; i *= 2) {
        if(i & exp) {
            answer = (answer * aux) % P;
        }
        aux = (aux * aux) % P;
    }

    return answer;
}

const long long INV_BASE_1 = pow(BASE, P1 - 2, P1);
const long long INV_BASE_2 = pow(BASE, P2 - 2, P2);

struct Hash {
    long long r1, r2;
    int len;

    Hash() {
        this->r1 = this->r2 = this->len = 0;
    }

    bool operator ==(const Hash &other) const {
        return (this->r1 == other.r1 &&
                this->r2 == other.r2 &&
                this->len == other.len);
    }
};

Hash push_back(Hash h, char c) {
    Hash answer;
    answer.r1 = (h.r1 * BASE + c - 'A') % P1;
    answer.r2 = (h.r2 * BASE + c - 'A') % P2;
    answer.len = h.len + 1;

    return answer;
}

Hash pop_front(Hash h, char c) {
    Hash answer;
    answer.r1 = (h.r1 - (c - 'A') * pow(BASE, h.len - 1, P1) + BASE * P1) % P1;
    answer.r2 = (h.r2 - (c - 'A') * pow(BASE, h.len - 1, P2) + BASE * P2) % P2;
    answer.len = h.len - 1;

    return answer;
}

Hash getHash(char *s) {
    Hash answer;
    while(*s != '\0') {
        answer = push_back(answer, *s);
        s++;
    }

    return answer;
}

char P[MAX_LEN], T[MAX_LEN];
vector <int> sol;

int main() {

    gets(P); gets(T);
    int len1 = strlen(P), len2 = strlen(T);

    Hash h1 = getHash(P), h2;
    for(int i = 0; i < min(len2, len1); i++) {
        h2 = push_back(h2, T[i]);
    }

    if(h1 == h2) {
        sol.push_back(len1 - 1);
    }

    //printf("%lld %lld %d\n", h1.r1, h1.r2, h1.len);
    //printf("%lld %lld %d\n", h2.r1, h2.r2, h2.len);

    for(int i = len1; i < len2 && sol.size() < 1000; i++) {
        h2 = push_back(h2, T[i]);
        h2 = pop_front(h2, T[i - len1]);
        //printf("%lld %lld %d\n", h2.r1, h2.r2, h2.len);

        if(h1 == h2) {
            sol.push_back(i - len1 + 1);
        }
    }

    printf("%d\n", (int)sol.size());
    for(int ind : sol) {
        printf("%d ", ind);
    }
}