Cod sursa(job #3369341)

Utilizator Maya_PopaPopa Maya Diana Maya_Popa Data 19 octombrie 2026 19:41:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <fstream>
#include <vector>
#define MOD 1000000007
#define BASE 101

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long get_val(char c) {
    if (c>='a' && c<='z') {
        return c-'a'+1;
    }
    if (c>='A' && c<='Z') {
        return c-'A'+27;
    }
    if (c>='0' && c<='9') {
        return c-'0'+53;
    }
    return 1;
}
int main() {
    int n,m,i,limit;
    long long hasha,hashb,p;
    string a, b;
    fin>>a>>b;
    n=a.length();
    m=b.length();
    if (n>m) {
        fout<<0<<"\n";
        return 0;
    }
    hasha=0;
    hashb=0;
    p=1;
    for (i=0; i<n-1; i++) {
        p=(p*BASE)%MOD;
    }
    for (i=0; i<n; i++) {
        hasha=(hasha*BASE+get_val(a[i]))%MOD;
        hashb=(hashb*BASE+get_val(b[i]))%MOD;
    }
    vector<int> v;
    if (hasha==hashb) {
        v.push_back(0);
    }
    for (i=n; i<m; i++) {
        hashb=(hashb-get_val(b[i-n])*p%MOD+MOD)%MOD;
        hashb=(hashb*BASE+get_val(b[i]))%MOD;
        if (hasha==hashb) {
            v.push_back(i-n+1);
        }
    }
    fout<<v.size()<<"\n";
    limit=min((int)v.size(), 1000);
    for (i=0; i<limit; i++) {
        fout<<v[i]<<" ";
    }
    return 0;
}