Cod sursa(job #2299562)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 9 decembrie 2018 18:31:31
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

const int base = 73, mod1 = 100007, mod2 = 100021;

string s, t;

vector<int> ans;

int main()
{
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    getline(fin, s);
    getline(fin, t);
    int lens = int(s.size()), lent = int(t.size()), high1 = 1, high2 = 1;
    int hashs1 = 0, hashs2 = 0, hasht1 = 0, hasht2 = 0;
    for(int i = 0; i < lens; ++i){
        hashs1 = (base * hashs1 + s[i]) % mod1;
        hashs2 = (base * hashs2 + s[i]) % mod2;
        hasht1 = (base * hasht1 + t[i]) % mod1;
        hasht2 = (base * hasht2 + t[i]) % mod2;
        if(i > 0){
            high1 = (high1 * base) % mod1;
            high2 = (high2 * base) % mod2;
        }
    }
    if(hashs1 == hasht1 && hashs2 == hasht2)
        ans.push_back(0);
    for(int i = lens; i < lent; ++i){
        hasht1 = ((hasht1 - (high1 * t[i - lens]) % mod1 + mod1) * base + t[i]) % mod1;
        hasht2 = ((hasht2 - (high2 * t[i - lens]) % mod2 + mod2) * base + t[i]) % mod2;
        if(hashs1 == hasht1 && hashs2 == hasht2)
            ans.push_back(i - lens + 1);
    }
    fout << ans.size() << "\n";
    for(int i = 0; i < int(ans.size()) && i < 1000; ++i)
        fout << ans[i] << " ";
    return 0;
}