Cod sursa(job #3171088)

Utilizator Cyrex.1948Dumitrica Cezar Stefan Cyrex.1948 Data 18 noiembrie 2023 12:52:51
Problema Potrivirea sirurilor Scor 22
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <fstream>
#include <vector>
#include <string>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
using namespace std;

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

const int MOD = 666013;
const int BASE = 101;
int cnt;
vector<int> rez;

void HashFunc(string pattern, string str){
    int M = pattern.size();
    int N = str.size();
    int pattern_hash = 0;
    int str_hash = 0;
    int power = 1;
    for(int i = 0; i <  M - 1; i++)
        power = (power * BASE) % MOD;
    for (int i = 0; i < M; i++) {
        pattern_hash = (BASE * pattern_hash + pattern[i]) % MOD;
        str_hash = (BASE * str_hash + str[i]) % MOD;
    }
    int j;
    for (int i = 0; i <= N - M; ++i) {
        if (pattern_hash == str_hash) {
            for (j = 0; j < M; ++j) {
                if (str[i + j] != pattern[j])
                    break;
            }
            if (j == M) {
                if (rez.size() < 1000) {
                    rez.push_back(i);
                }
                cnt++;
            }
        }
        if (i < N - M) {
            str_hash = (BASE * (str_hash - str[i] * power) + str[i + M]) % MOD;
            if (str_hash < 0)
                str_hash += MOD;
        }
    }
}

signed main(){
    ios;
    string pattern, str;
    cin >> pattern >> str;
    HashFunc(pattern, str);
    cout << cnt << '\n';
    for (int i = 0; i < rez.size(); i++) {
        cout << rez[i] << ' ';
    }
    return 0;
}