Cod sursa(job #2976484)

Utilizator SerbanCaroleSerban Carole SerbanCarole Data 9 februarie 2023 11:40:12
Problema Potrivirea sirurilor Scor 16
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <bits/stdc++.h>
using namespace std;

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

const int b = 256;
const int MOD = INT_MAX;

string p , t;

vector <int> poz;

int main(){

    fin >> p >> t;

    int n = t.size();
    int m = p.size();

    int hashp = 0 , hasht = 0 , h = 1;

    for(int i = 0 ; i < m - 1 ; i++){

        h = ( h * b )%MOD;
    }

    for(int i = 0 ; i < m ; i++){

        hashp = (hashp*b + p[i])%MOD;
        hasht = (hasht*b + t[i])%MOD;
    }

    if(hashp == hasht) poz.push_back(0);

    for(int i = 1 ; ( i + m - 1 ) < n ; i++){

        hasht = (((hasht - (t[i-1]*h)%MOD) * b)%MOD + t[( i + m - 1 )])%MOD;

        if(hasht == hashp) poz.push_back(i);

    }

    fout << poz.size()<< '\n';

    for( auto it : poz ){

        fout << it << ' ';
    }

    return 0;
}