Cod sursa(job #2180175)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 20 martie 2018 17:53:44
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
     
using namespace std;
     
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

typedef long long int ll;
const int P = 31;

vector < int > RabinKarp(const string &A, const string &B) {
    vector < ll > power(max(A.size(), B.size()));
    power[0] = 1;
    for(int i = 1; i < (int)power.size(); ++i) {
        power[i] = power[i - 1] * P;
    }

    ll hA = 0;
    for(int i = 0; i < (int)A.size(); ++i) {
        hA = hA + (A[i] - 'A') * power[i];
    }

    vector < ll > hash((int)B.size());
    for(int i = 0; i < (int)B.size(); ++i) {
        hash[i] = (B[i] - 'A') * power[i];
        if(i) hash[i] += hash[i - 1];
    }

    vector < int > ret;

    for(int i = 0; i + (int)A.size() - 1 < (int)B.size(); ++i) {
        ll curHash = hash[i + (int)A.size() - 1];
        if(i) curHash -= hash[i - 1];
        
        if(curHash == hA * power[i]) {
            ret.push_back(i);
        }
    }
 
    return ret;
}
 
int main() {
    string A, B;
    fin >> A >> B;
 
    vector < int > ans = RabinKarp(A, B);
 
    fout << (int)ans.size() << "\n";
    for(int i = 0; i < min((int)ans.size(), 1000); ++i) fout << ans[i] << " ";
    return 0;
}