Cod sursa(job #2988006)

Utilizator pifaDumitru Andrei Denis pifa Data 3 martie 2023 12:26:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string s, t;
    cin >> s >> t;
    const int p = 31;
    vector <long long> p_pow(max(s.size(), t.size()));
    p_pow[0] = 1;
    for(int i = 1; i < p_pow.size(); i++)
        p_pow[i] = p_pow[i - 1] * p;
    vector <long long> h(t.size());
    for(int i = 0; i < t.size(); i++)
    {
        h[i] = (t[i] - 'A' + 1) * p_pow[i];
        if(i)
            h[i] += h[i - 1];
    }
    long long hs = 0;
    for(int i = 0; i < s.size(); i++)
    {
        hs += (s[i] - 'A' + 1) * p_pow[i];
    }
    vector <int> a;
    for(int i = 0; i + s.size() - 1 < t.size(); i++)
    {
        long long cur_h = h[i + s.size() - 1];
        if(i)
            cur_h -= h[i - 1];
        if(cur_h == hs * p_pow[i])
            a.push_back(i);
    }
    cout << a.size() << '\n';
    for(auto x:a)
        cout << x << ' ';
    return 0;
}