Cod sursa(job #3369706)

Utilizator VladGtjGatej Vlad VladGtj Data 21 octombrie 2026 19:44:28
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <fstream>
#define MOD 1000000007
#define BASE 77

using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
long long value(char ch) {
    if(ch>='0' && ch<='9'){
        return ch-'0';
    }
    if(ch>='a' && ch<='z'){
        return ch-'a'+10;
    }
    if(ch>='A' && ch<='Z'){
        return ch-'A'+37;
    }
    return 1;
}
int main() {
    int n,m,i;
    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+value(a[i]))%MOD;
        hashb=(hashb*BASE+value(b[i]))%MOD;
    }
    int v[2000000];
    int vInd=1;
    if (hasha==hashb) {
        v[vInd++]=0;
    }
    for (i=n; i<m; i++) {
        hashb=(hashb-value(b[i-n])*p%MOD+MOD)%MOD;
        hashb=(hashb*BASE+value(b[i]))%MOD;
        if (hasha==hashb) {
            v[vInd++]=i-n+1;
        }
    }
    fout<<vInd-1<<"\n";
    for (i=1; i<=vInd-1; i++) {
        fout<<v[i]<<" ";
    }
    return 0;
}