Cod sursa(job #983638)

Utilizator florin.elfusFlorin Elfus florin.elfus Data 12 august 2013 14:28:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
//Rabin Karp

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#define REP(i, a, b) for(int i = a; i <= b; ++i)
#define FOR(i, n) REP(i, 1, n)
#define FOREACH(i, t) for (typeof(t.begin()) i = t.begin(); i != t.end(); ++i)
#define max(a, b) (a > b ? a : b)
#define min(a, b) (a < b ? a : b)
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define read(n) int (n); scanf("%d", &(n))
#define read2(n, m) int (n), (m); scanf("%d %d", &(n), &(m))
#define read3(n, m, k) int (n), (m), (k); scanf("%d %d %d", &(n), &(m), &(k))
#define ll long long
#define x first
#define y second
#define mp make_pair
#define B 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

char pat[2000100], S[2000100];
int matches[2000100];

int main() {
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    gets(pat + 1); gets(S + 1);
    int cntP = strlen(pat + 1), cntS = strlen(S + 1);
    if (cntP > cntS) {
        printf("0");
        return 0;
    }

    int hash1 = 0, hash2 = 0, cur1 = 0, cur2 = 0, pw1 = 1, pw2 = 1, cpw1, cpw2;
    for (int i = cntP; i >= 1; --i) {
        cpw1 = pw1; cpw2 = pw2;
        hash1 += pw1 * pat[i];
        hash2 += pw2 * pat[i];
        cur1 += pw1 * S[i];
        cur2 += pw2 * S[i];
        hash1 %= MOD1; hash2 %= MOD2;
        cur1 %= MOD1; cur2 %= MOD2;
        pw1 *= B; pw2 *= B;
        pw1 %= MOD1; pw2 %= MOD2;
    }

    pw1 = cpw1; pw2 = cpw2;
    REP(i, cntP, cntS) {
        if (cur1 == hash1 && cur2 == hash2)
            matches[++matches[0]] = i - cntP;
        cur1 = ((cur1 - pw1 * S[i - cntP + 1] % MOD1 + MOD1) * B + S[i + 1]) % MOD1;
        cur2 = ((cur2 - pw2 * S[i - cntP + 1] % MOD2 + MOD2) * B + S[i + 1]) % MOD2;
    }

    printf("%d\n", matches[0]);
    chmin(matches[0], 1000);
    FOR(i, matches[0])
        printf("%d ", matches[i]);
    return 0;
}