Cod sursa(job #2777194)

Utilizator MihaiZ777MihaiZ MihaiZ777 Data 22 septembrie 2021 16:11:51
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.96 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string a, b;
int generalHash1;
int generalHash2;
vector <int> pos;

const int MOD1 = 664918;
const int MOD2 = 5762209;
const int BASE1 = 139;
const int BASE2 = 131;




int Hash(string str, const int& modulo, const int& base)
{
    long long myHash = 0;

    for (int i = 0; i < str.size(); i++)
    {
        myHash *= base;
        myHash += str[i];
        myHash %= modulo;
    }

    return myHash;
}


int main()
{
    fin >> a >> b;
    generalHash1 = Hash(a, MOD1, BASE1);
    generalHash2 = Hash(a, MOD2, BASE2);


    if (a.size() > b.size())
    {
        fout << 0 << '\n';
    }

    int currentHash1 = Hash(b.substr(0, a.size()), MOD1, BASE1);
    int currentHash2 = Hash(b.substr(0, a.size()), MOD2, BASE2);

    if (generalHash1 == currentHash1 && generalHash2 == currentHash2)
    {
        pos.push_back(0);
    }

    int basePow1 = 1;
    int basePow2 = 1;
    for (int i = 1; i < a.size(); i++)
    {
        basePow1 *= BASE1;
        basePow1 %= MOD1;
        basePow2 *= BASE2;
        basePow2 %= MOD2;
    }

    for (int i = a.size(); i < b.size(); i++)
    {
        int index = i - a.size();

        int x1 = (b[index] * basePow1) % MOD1;
        currentHash1 = ((currentHash1 - x1 + MOD1) % MOD1) * BASE1;
        currentHash1 += b[i];
        currentHash1 %= MOD1;

        int x2 = (b[index] * basePow2) % MOD2;
        currentHash2 = ((currentHash2 - x2 + MOD2) % MOD2) * BASE2;
        currentHash2 += b[i];
        currentHash2 %= MOD2;

        if (generalHash1 == currentHash1 && generalHash2 == currentHash2)
        {
            pos.push_back(index + 1);
        }
    }
    fout << pos.size() << '\n';
    for (int x : pos)
    {
        fout << x << ' ';
    }
    fout << '\n';

    return 0;
}