Cod sursa(job #3215025)

Utilizator MerlinTheWizardMelvin Abibula MerlinTheWizard Data 14 martie 2024 17:13:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include<bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int MOD = 100007;
string a, b;
vector<int> ans;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin >> a >> b;

    long long hash1 = 0, hash2 = 0;

    for(int i = 0; i < a.size(); i++)
    {
        hash1 *= 2;
        hash1 += (a[i] - 'A');
        hash1 %= MOD;
    }

    for(int i = 0; i < a.size(); i++)
    {
        hash2 *= 2;
        hash2 += (b[i] - 'A');
        hash2 %= MOD;
    }

    if(hash1 == hash2)
        ans.push_back(0);

    for(int i = a.size(); i < b.size(); i++)
    {
        hash2 *= 2;
        hash2 -= (1LL << a.size()) * (b[i - a.size()] - 'A');
        hash2 += (b[i] - 'A');
        hash2 %= MOD;
        if(hash1 == hash2)
            ans.push_back(i - a.size());
        cerr << hash1 << " " << hash2 << "\n";
    }

    cout << ans.size() << "\n";
    int n = ans.size();
    for(int i = 0; i < min(999, n); i++)
        cout << ans[i] + 1<< " ";
}