Cod sursa(job #2910115)

Utilizator matwudemagogul matwu Data 18 iunie 2022 15:45:26
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int x1, x2, y5, y2;
long long const m1 = 10e9 + 7;
long long const m2 = 10e9 + 3;

vector<int> v;
int main(){

    fin >> a >> b;
    int p1 =1 , p2 = 1;
    for(int i = 0; i < a.length(); i++){
        if(i){
        p1 = (p1 * 26) % m1;
        p2 = (p2 * 26) % m2;
        }
        x1 = (x1 * 26 + a[i] - 'A') % m1;
        x2 = (x2 * 26 + a[i] - 'A') % m2;
        y5 = (y5 * 26 + b[i] - 'A') % m1;
        y2 = (y2 * 26 + b[i] - 'A') % 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]- 'A') * p1) % m1 + m1) % m1) * 26 + b[i + a.length() - 1] - 'A' ) % m1;
        y2 = (((y2 - ((b[i - 1]- 'A') * p2) % m2 + m2) % m2) * 26 + b[i + a.length() - 1] - 'A' ) % 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] << " ";  
}