Cod sursa(job #2011632)

Utilizator LucaSeriSeritan Luca LucaSeri Data 16 august 2017 19:28:09
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>

using namespace std;

const int P = 73;
const int MOD1 = 100007;
const int MOD2 = 100021;

vector <int> sol;

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

int main()
{
    string a;
    string b;
    cin >> a >> b;
    int P1 = 1, P2 = 1;
    int s1 = 0, s2 = 0;
    for(int i = 0;i < a.size(); ++i){
        s1 = (s1 * P + a[i]) % MOD1;
        s2 = (s2 * P + a[i]) % MOD2;

        if(i != 0){
            P1 = P1 * P % MOD1;
            P2 = P2 * P % MOD2;
        }
    }
    int hash1 = 0, hash2 = 0;
    for(int i = 0; i < a.size(); ++i){
        hash1 = (hash1 * P + b[i]) % MOD1;
        hash2 = (hash2 * P + b[i]) % MOD2;
    }
    int nr = 0;
    if(hash1 == s1 && hash2 == s2){
        sol.push_back(1);
        ++nr;
    }

    for(int i = a.size(); i < b.size(); ++i){
        hash1 = (((hash1 - b[i-a.size()] * P1) % MOD1 + MOD1) * P + b[i]) % MOD1;
        hash2 = (((hash2 - b[i-a.size()] * P2) % MOD2 + MOD2) * P + b[i]) % MOD2;

        if(hash1 == s1 && hash2 == s2){
            sol.push_back(i-a.size() + 1);
            ++nr;
        }
    }

    cout << nr << '\n';
    for(int i = 0; i < min(1000, nr); ++i){
        cout << sol[i] << ' ';
    }
    return 0;
}