Cod sursa(job #3275502)

Utilizator arrckerArdeleanu Aris Matei arrcker Data 10 februarie 2025 19:55:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 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 133
#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;


    if(pattern.size() > text.size())
    {
        fout << 0;
        return 0;
    }



    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 == t1  &&  p2 == t2) v[++n] = 0;


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

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


    fout << n <<nn;

    for(int i=1; i<=min(n,1LL*1000); ++i)
        fout << v[i] <<" ";
}