Cod sursa(job #2721305)

Utilizator nicolaefilatNicolae Filat nicolaefilat Data 11 martie 2021 18:22:46
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <vector>

const int baza = 27 * 2 + 10;
const int MOD1 = 1e9 + 7;

using namespace std;

const int MAXN = 2e6;

typedef long long ll;

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

typedef long long ll;

string a,b;
ll putere[MAXN];

int ascii(char c){
    return int(c - 'A' + 1);
}

int main()
{
    in>>a>>b;
    ll p = 1;
    for(int i = 0; i < a.size(); i++){
        putere[i] = p;
        p = (p * baza) % MOD1;
    }
    ll hasha = 0;
    for(int i = 0; i < a.size(); i++){
        hasha = ((hasha * baza + ascii(a[i]) + MOD1)) % MOD1;
//        cout<<hasha<<" "<<ascii(a[i])<<endl;
    }
//    cout<<hasha<<endl;
    ll hashb = 0;
    for(int i = 0; i < a.size(); i++){
        hashb = ((hashb * baza + ascii(b[i]) + MOD1)) % MOD1;
    }
    vector<int>ap;
    if(hasha == hashb){
        ap.push_back(0);
    }
    for(int i = a.size(); i < b.size(); i++){
        hashb = hashb - ascii(b[i - a.size()]) * putere[a.size() - 1];
        hashb = (hashb * baza + ascii(b[i])) % MOD1;
        hashb = (hashb + MOD1) % MOD1;
        if(hasha == hashb)
            ap.push_back(i - a.size() + 1);
    }
    out<<ap.size()<<'\n';
    for(int i = 0; i < min(1000,int(ap.size())); i++)
        out<<ap[i]<<" ";

    return 0;
}