Cod sursa(job #2910685)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 24 iunie 2022 09:50:49
Problema Potrivirea sirurilor Scor 86
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;

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

string a, b;
long long x1, x2, y5, y2;
long long const m1 = 10e6 + 7;
long long const m2 = 10e6 + 3;

vector < int > v;

int main(){

    fin >> a >> b;
    long long p1 = 1, p2 = 1;
    for(int i = 0; i < a.length(); i++){
        if(i){
        p1 = (p1 * 123) % m1;
        p2 = (p2 * 123) % m2;
        }
        x1 = (x1 * 123 + a[i]) % m1;
        x2 = (x2 * 123 + a[i]) % m2;
        y5 = (y5 * 123 + b[i]) % m1;
        y2 = (y2 * 123 + b[i]) % m2;

    }

    if(x1 == y5 && x2 == y2) v.push_back(0);

    for(int i = 1; i < b.length() - a.length() + 1; i++){

        y5 = (((y5 - ((b[i - 1]) * p1) % m1 + m1) % m1) * 123 + b[i + a.length() - 1]) % m1;
        y2 = (((y2 - ((b[i - 1]) * p2) % m2 + m2) % m2) * 123 + b[i + a.length() - 1]) % m2;
        if(x1 == y5 && x2 == y2) v.push_back(i);
    }

    fout << v.size() << '\n';
    int s = v.size();
    for(int i = 0; i < min(s, 1000); i++)
        fout << v[i] << ' ';
}