Cod sursa(job #2534390)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 30 ianuarie 2020 15:50:46
Problema Potrivirea sirurilor Scor 92
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

#define PRIME   31
#define MOD2    100007
#define MOD1    100021

std::pair <int, int> hash(const std::string &str) {
    std::pair <int, int> ans(0, 0);
    int p1 = 1, p2 = 1;
    for (int i=str.size()-1; i>=0; --i)
        ans.first  = (ans.first  + (str[i]-'A')*p1)%MOD1, p1 = (p1*PRIME)%MOD1,
        ans.second = (ans.second + (str[i]-'A')*p2)%MOD2, p2 = (p2*PRIME)%MOD2;
    return ans;
}

std::string t, s;
std::pair <int, int> hash_t;

std::ifstream   input ("strmatch.in");
std::ofstream   output("strmatch.out");

int main()
{
    input >> t >> s;
    int len_t = t.size();
    hash_t = hash(t);

    if (t.size() > s.size()) {
        output << 0;
        return 0;
    }

    int pp1 = 1, pp2 = 1;
    for (int i=0; i<len_t; ++i)
        pp1 = (pp1*PRIME)%MOD1, pp2 = (pp2*PRIME)%MOD2;

    std::vector <int> sol;
    std::pair <int, int> val = hash(s.substr(0, len_t));
    if (val == hash_t) sol.push_back(0);
    for (int i=len_t; i<s.size(); ++i) {
        val.first  = (val.first*PRIME  + (s[i]-'A') - (s[i-len_t]-'A')*pp1 % MOD1 + MOD1)%MOD1;
        val.second = (val.second*PRIME + (s[i]-'A') - (s[i-len_t]-'A')*pp2 % MOD2 + MOD2)%MOD2;
        if (val == hash_t) sol.push_back(i-len_t+1);
    }

    output << sol.size() << '\n';
    for (int i=0; i<sol.size() && i<1000; ++i)
        output << sol[i] << ' ';

    return 0;
}