Cod sursa(job #2965304)

Utilizator VladLuncanLuncan Vlad VladLuncan Data 14 ianuarie 2023 20:02:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.8 kb
#include <fstream>
#include <vector>
#define p 31

using namespace std;

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

string a, b;
unsigned long long h1, h2, p_n = 1;
vector<int> result;

void calculate_hashes()
{
    for (int i = 0; i < a.size(); ++i)
        h1 = h1 * p + a[i],
        h2 = h2 * p + b[i],
        p_n *= p;
}

int main()
{
    cin >> a >> b;

    calculate_hashes();
    if (h1 == h2)
        result.push_back(0);

    for (int i = a.size(); i < b.size(); ++i)
    {
        h2 = h2 * p + b[i] - b[i - a.size()] * p_n;
        if (h1 == h2)
            result.push_back(i - a.size() + 1);
    }

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

    return 0;
}