Cod sursa(job #3174019)

Utilizator Radu_MocanasuMocanasu Radu Radu_Mocanasu Data 24 noiembrie 2023 10:31:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 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 val[150];
void genp(){
    int i,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, hash_pre1 = 0, hash_pre2 = 0,p1 = 1, p2 = 1;
    genp();
    fin >> s;
    fin.get();
    fin >> ch;
    sz = strlen(s);
    n = strlen(ch);
    for(i = 0; i < sz; i++){
        hash1_s = (hash1_s * base + val[s[i]]) % mod1;
        hash2_s = (hash2_s * base +  val[s[i]]) % mod2;
        hash_pre1 = (hash_pre1 * base + val[ch[i]]) % mod1;
        hash_pre2 = (hash_pre2 * base + val[ch[i]]) % mod2;
        if(i != 0){
            p1 = (p1 * base) % mod1;
            p2 = (p2 * base) % mod2;
        }
    }
    if(hash1_s == hash_pre1 && hash2_s == hash_pre2){
        k++;
        rez.push_back(i - sz);
    }
    for(i = sz; i < n; i++){
        hash_pre1 = 1LL * ((hash_pre1 - (val[ch[i - sz]] * p1) % mod1 + mod1) * base + val[ch[i]]) % mod1;
        hash_pre2 = 1LL * ((hash_pre2 - (val[ch[i - sz]] * p2) % mod2 + mod2) * base + val[ch[i]]) % mod2;
        if(hash1_s == hash_pre1 && hash2_s == hash_pre2){
            k++;
            rez.push_back(i - sz + 1);
        }
    }
    fout << k << "\n";
    for(auto x : rez) fout << x << " ";
    return 0;
}