Cod sursa(job #2137355)

Utilizator oso.andinoooIonut Stan oso.andinooo Data 20 februarie 2018 19:05:44
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int N = 2000005, BASE = 131, MOD1 = 666013, MOD2 = 666019;

struct Hash {
    int a, b; };

static bool operator == (const Hash &u, const Hash &v) {
    return u.a == v.a && u.b == v.b; }

char s1[N], s2[N];

vector<int> aps;
Hash pattern, window;
int n, m;

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

    gets(s1); n = strlen(s1);
    gets(s2); m = strlen(s2);

    pwr1 = pwr2 = 1;
    for (int i = 1; i < n; ++i) {
        pwr1 = pwr1 * BASE % MOD1;
        pwr2 = pwr2 * BASE % MOD2; }

    if (n > m) {
        puts("0");
        return 0; }

    pattern = window = {0, 0};
    for (int i = 0; i < n; ++i) {
        pattern.a = (pattern.a * BASE + s1[i]) % MOD1;
        pattern.b = (pattern.b * BASE + s1[i]) % MOD2; }

    for (int i = 0; i < n; ++i) {
        window.a = (window.a * BASE + s2[i]) % MOD1;
        window.b = (window.b * BASE + s2[i]) % MOD2; }

    if (pattern == window)
        aps.push_back(0);

    for (int i = 1; i + n - 1 < m; ++i) {
        window.a = ((((window.a - pwr1 * s2[i - 1]) * BASE + s2[i + n - 1]) % MOD1) + MOD1) % MOD1;
        window.b = ((((window.b - pwr2 * s2[i - 1]) * BASE + s2[i + n - 1]) % MOD2) + MOD2) % MOD2;
        if (pattern == window)
            aps.push_back(i); }

    printf("%d\n", aps.size());
    for (int i = 0; i < min(1000, int(aps.size()));i++) {
        printf("%d ", aps[i]); }
    printf("\n");

    return 0; }