Cod sursa(job #3183734)

Utilizator octavian202Caracioni Octavian Luca octavian202 Data 12 decembrie 2023 22:11:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <iostream>
#include <fstream>
#include <vector>

#define ll long long

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const ll MOD = 1e9 + 7;
ll p = 31;
ll putere[2000005];
string s, t;
ll hs, ht, n, m;

bool check(int ind) {
    for (int i = ind; i < ind + n; i++) {
        if (s[i - ind] != t[i])
            return false;
    }
    return true;
}

vector<int> res;

int main() {

    fin >> s >> t;

    n = s.size();
    m = t.size();

    putere[0] = 1;
    for (int i = 1; i <= n; i++) {
        putere[i] = (putere[i - 1] * p) % MOD;
    }

    for (int i = n - 1; i >= 0; i--) {
        hs = (hs + putere[n - i - 1] * (ll)(s[i] - 'A' + 1)) % MOD;
        ht = (ht + putere[n - i - 1] * (ll)(t[i] - 'A' + 1)) % MOD;
    }
//cout << hs << '\n';

    for (int i = 0; i < m - n; i++) {
        if (hs == ht) {
            if (check(i))
                res.push_back(i);
        }
//        cout << ht << ' ';

        ht = (ht - putere[n - 1] * (ll)(t[i] - 'A' + 1) + MOD) % MOD;
        ht = ((ht * p) % MOD + (t[i + n] - 'A' + 1)) % MOD;
    }

    int nr = res.size();
    fout << nr << '\n';
    for (int i = 0; i < min(1000, nr); i++)
        fout << res[i] << ' ';




    return 0;
}