Cod sursa(job #3157193)

Utilizator Roxana_3Asavei Roxana Roxana_3 Data 14 octombrie 2023 17:24:53
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.08 kb
#include <bits/stdc++.h>
#define N 2000000
#define B 127
#define MOD 666013
using namespace std;

/// cautam aparitiile lui a in b

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

char a[N + 5], b[N + 5];
int nr_ap, poz[1005];
int len_a, len_b;

bool Match(int st)
{
    for(int i = 0; i < len_a; ++i)
        if(a[i] != b[st + i]) return 0;
    return 1;
}

int main()
{
    fin >> a >> b;
    int first_ch = 1;
    int pattern_hash = 0;

    len_a = strlen(a);
    len_b = strlen(b);

    if(len_a > len_b) {cout << 0; return 0;}

    /// calculam valoarea aferenta lui A
    for(int i = len_a - 1; i >= 0; --i)
    {
        pattern_hash = (pattern_hash % MOD + (int(a[i]) * first_ch) % MOD) % MOD;
        first_ch = (first_ch * B) % MOD;
    }

    first_ch = 1;
    for(int i = 1; i < len_a; ++i)
        first_ch = (first_ch * B) % MOD;

    int current_hash = 0;
    int pow = 1;
    /// calculam valoarea primei ferestre
    for(int i = len_a - 1; i >= 0; --i)
        {
            current_hash = (current_hash % MOD + (int(b[i]) * pow) % MOD) % MOD;
            pow = (pow * B) % MOD;
        }

    /// verificam daca avem un match
    if(current_hash == pattern_hash && Match(0))
        poz[nr_ap++] = 0;

   /// calculam pt restul ferestrelor
   for(int i = len_a; i < len_b; ++i)
   {
       if(current_hash <= int(b[i - len_a]) * first_ch)
       {
           int ct = (int(b[i - len_a]) * first_ch - current_hash) / MOD;
           current_hash += (ct + 1) * MOD; // tb liniarizat
       }
       current_hash = (current_hash - int(b[i - len_a]) * first_ch) % MOD;
       current_hash = (current_hash * B) % MOD; /// tot ce pastrez avanseaza cu o poz in stanga, deci puterea la care apare B creste cu 1 pt fiecare
       current_hash = (current_hash % MOD + int(b[i]) % MOD) % MOD;
       if(current_hash == pattern_hash && Match(i - len_a + 1) && nr_ap < 1000)
                poz[nr_ap++] = i - len_a + 1;
   }

   fout << nr_ap << "\n";
   for(int i = 0; i < nr_ap; ++i)
        fout << poz[i] << " ";


    return 0;
}