Cod sursa(job #3159436)

Utilizator Maftei_TudorMaftei Tudor Maftei_Tudor Data 21 octombrie 2023 12:26:37
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <vector>
#include <cstring>

#define pb push_back

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 2e6 + 5, mod = 1e9 + 7;
typedef long long ll;

ll n, hsh;
char c1[N], c2[N];
vector<int> ans;

int main()
{
    in >> c1;
    in >> c2;

    const int ptr = strlen(c2) - strlen(c1);
    const int lg = strlen(c1);

    int p = 1;
    for(int i=0; i<lg; i++) {
        n += p * (c1[i] - 'A' + 1);
        p *= 50;
        if(n >= mod)
            n %= mod;
        if(p >= mod)
            p %= mod;
    }

    p = 1;
    for(int i=ptr; i<strlen(c2); i++) {
        hsh += p * (c2[i] - 'A' + 1);
        if(i < strlen(c2) - 1)
            p *= 50;

        if(hsh >= mod)
            hsh %= mod;
        if(p >= mod)
            p %= mod;
    }
    if(hsh == n)
        ans.pb(ptr);

    for(int i=ptr-1; i>=0; i--) {
        hsh = ((hsh - (c2[i+lg] - 'A' + 1) * p % mod) + mod) % mod;
        hsh *= 50;
        if(hsh >= mod)
            hsh %= mod;
        hsh += c2[i] - 'A' + 1;
        if(hsh >= mod)
            hsh %= mod;

        if(hsh == n)
            ans.pb(i);
    }

    out << ans.size() << '\n';
    for(int i=ans.size()-1; i>=0; i--)
        out << ans[i] << ' ';
    return 0;
}