Cod sursa(job #2938615)

Utilizator VladLuncanLuncan Vlad VladLuncan Data 12 noiembrie 2022 13:35:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;

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

string s1, s2;
unsigned long long h1, h2, p_n = 1;
long long p = 31;
vector<int> rez;

int main()
{
    cin >> s1 >> s2;
    if (s1.size() > s2.size())
        swap(s1, s2);
    for (int i = 0; i < s1.size(); ++i)
        h1 = h1 * p + s1[i],
        h2 = h2 * p + s2[i],
        p_n = p_n * p;
    if (h1 == h2)
        rez.push_back(0);
    for (int i = s1.size(); i < s2.size(); ++i)
    {
        h2 = h2 * p + s2[i] - s2[i - s1.size()] * p_n;
        if (h1 == h2)
            rez.push_back(i - s1.size() + 1);
    }
    cout << rez.size() << '\n';
    for (int i = 0; i < min(1000, (int)rez.size()); ++i)
        cout << rez[i] << ' ';

    return 0;
}