Cod sursa(job #3256064)

Utilizator adimiclaus15Miclaus Adrian Stefan adimiclaus15 Data 13 noiembrie 2024 10:32:00
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.96 kb
#include <fstream>
#include <vector>
#include <unordered_map>

using namespace std;
const int NMAX = 2000000;
using ll = long long;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

unordered_map <char, int> umap;

int b1 = 67, MOD1 = 1e9 + 7, b2 = 71, MOD2 = 100076969;
ll prec1[NMAX + 2], prec2[NMAX + 2];

void init() {
    ///map
    for(char i = 'A'; i <= 'Z'; i++)
        umap[i] = i - 'A' + 1;
    for(char i = 'a'; i <= 'z'; i++)
        umap[i] = (i - 'a' + 1) + 26;
    for(char i = '0'; i <= '9'; i++)
        umap[i] = (i - '0' + 1) + 52;

    prec1[0] = 1; prec2[0] = 1;
    for(int i = 1; i <= NMAX; i++) {
        prec1[i] = (prec1[i - 1] * b1) % MOD1;
        prec2[i] = (prec2[i - 1] * b2) % MOD2;
    }
}

int logexp(ll a, int n, int MOD) {
    ll p = 1;
    for(int k = 1; k <= n; k <<= 1) {
        if((n & k))
            p *= a;
        a *= a;
        p %= MOD;
        a %= MOD;
    }
    return p;
}

struct HASH {
    ll roll_hash1 = 0;
    ll roll_hash2 = 0;
    ll invb1 = logexp(b1, MOD1 - 2, MOD1);
    ll invb2 = logexp(b2, MOD2 - 2, MOD2);
    void add(int ch, int pos) {
        roll_hash1 = (roll_hash1 + umap[ch] * prec1[pos]) % MOD1;
        roll_hash2 = (roll_hash2 + umap[ch] * prec2[pos]) % MOD2;
    }
    void removee(int ch, int pos) {
        //cout << roll_hash1 << " ";
        roll_hash1 -= (umap[ch] * prec1[pos]);
        if(roll_hash1 < 0)
            roll_hash1 += MOD1;
        //cout << roll_hash1 << " ";
        roll_hash1 = (roll_hash1 * invb1) % MOD1;
        //cout << roll_hash1 << "  ";

        roll_hash2 -= (umap[ch] * prec2[pos]);
        if(roll_hash2 < 0)
            roll_hash2 += MOD2;
        roll_hash2 = (roll_hash2 * invb2) % MOD2;
    }
};

bool check(HASH a, HASH b) {
    if(a.roll_hash1 == b.roll_hash1 && a.roll_hash2 == b.roll_hash2)
        return true;
    return false;
}

vector <int> ans;
int main()
{
    init();
    string a, b;
    cin >> a >> b;
    HASH var1, var2;
    if(a.size() > b.size()) {
        cout << 0;
        return 0;
    }
    for(int i = 0; i < a.size(); i++) {
        var1.add(a[i], (i + 1));
        var2.add(b[i], (i + 1));
    }
    //cout << var1.roll_hash1 << " " << var1.roll_hash2 << '\n';
    //cout << var2.roll_hash1 << " " << var2.roll_hash2 << '\n';
    int sizee = 0;
    if(check(var1, var2)) {
        sizee++;
        ans.push_back(0);
    }
    for(int i = a.size(); i < b.size(); i++) {
        //cout << i << '\n';
        var2.removee(b[i - a.size()], 1);
        var2.add(b[i], a.size());
        //cout << var2.roll_hash1 << '\n';
        //cout << var1.roll_hash1 << " " << var1.roll_hash2 << '\n';
        //cout << var2.roll_hash1 << " " << var2.roll_hash2 << '\n';
        if(check(var1, var2)) {
            sizee++;
            if(sizee < 1000)
                ans.push_back(i - a.size() + 1);
        }
    }
    cout << sizee << '\n';
    for(auto x : ans)
        cout << x << " ";

    /*for(auto var : umap)
        cout << var.first << " " << var.second << '\n';*/
    return 0;
}