Cod sursa(job #3275475)

Utilizator arrckerArdeleanu Aris Matei arrcker Data 10 februarie 2025 19:23:01
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>
using namespace std;

#define nn "\n"
#define il inline
#define se second
#define fi first
#define pb push_back
#define pf push_front
#define in insert

#define int long long
#define b 135
#define mod1 100007
#define mod2 100021

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


string pattern,text;
int v[1003],n;
int h1 = 1, h2 = 1, p1,t1, p2,t2;


signed main()
{
    fin >> pattern >> text;



    for(int i=0; i<pattern.size(); ++i)
    {
        if(i != 0)
        {
            h1 = h1 * b % mod1;
            h2 = h2 * b % mod2;
        }

        p1 = (p1 * b + pattern[i]) % mod1;
        p2 = (p2 * b + pattern[i]) % mod2;

        t1 = (t1 * b + text[i]) % mod1;
        t2 = (t2 * b + text[i]) % mod2;
    }

    if(p1 == t2  &&  p1 == t1) v[++n] = 0;


    for(int i=pattern.size(); i<=text.size(); ++i)
    {
        t1 = ((t1 - (h1 * text[i - pattern.size()]) % mod1 + mod1) % mod1 * b + text[i]) % mod1;
        t2 = ((t2 - (h2 * text[i - pattern.size()]) % mod2 + mod2) % mod2 * b + text[i]) % mod2;

        if(p1 == t1 && p2 == t2  &&  n < 1000) v[++n] = i - pattern.size() + 1;
    }


    fout << n <<nn;

    for(int i=1; i<=n; ++i)
        fout << v[i] <<" ";
}