Cod sursa(job #3174006)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 24 noiembrie 2023 09:40:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
#define mod1 1000000007
#define mod2 1000000009
#define base 67
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector <int> rez;
char s[nmax];
char ch[nmax];
int hash_pre1[nmax];
//int hash_pre2[nmax];
int p1[nmax];
//int p2[nmax];
int val[150];
void genp(){
    int i;
    p1[0] =  1;
    //p2[0] = 1;
    for(i = 1; i <= nmax; i++){
        p1[i] = (1LL * p1[i - 1] * base) % mod1;
        //p2[i] = (1LL * p2[i - 1] * base) % mod2;
    }
    int c = 65;
    for(i = 1; i <= 26; i++){
        val[c] = i;
        c++;
    }
    c = 97;
    for( ; i <= 52; i++){
        val[c] = i;
        c++;
    }
    c = 48;
    for( ; i <= 62; i++){
        val[c] = i;
        c++;
    }
}
int main()
{
    int n,i,sz,k = 0;
    long long hash1_s = 0, hash2_s = 0;
    genp();
    fin >> s;
    fin.get();
    fin >> ch;
    sz = strlen(s);
    n = strlen(ch);
    for(i = 0; i < sz; i++){
        hash1_s = (hash1_s + 1LL * val[s[i]] * p1[i]) % mod1;
        //hash2_s = (hash2_s + 1LL * val[s[i]] * p2[i]) % mod2;
    }
    for(i = 0; i < n; i++){
        hash_pre1[i + 1] = 1LL * (hash_pre1[i] + 1LL * val[ch[i]] * p1[i]) % mod1;
        //hash_pre2[i + 1] = 1LL * (hash_pre2[i] + 1LL * val[ch[i]] * p2[i]) % mod2;
    }
    for(i = 0; i + sz - 1 < n; i++){
        long long c_hash1 = (1LL * (hash_pre1[i + sz] + mod1 - hash_pre1[i])) % mod1;
        //long long c_hash2 = (1LL * (hash_pre2[i + sz] + mod2 - hash_pre2[i])) % mod2;
        if(c_hash1 == hash1_s * p1[i] % mod1 /*&& c_hash2 == hash2_s * p2[i] % mod2*/){
            k++;
            rez.push_back(i);
        }
    }
    fout << k << "\n";
    for(auto x : rez) fout << x << " ";
    return 0;
}