Cod sursa(job #3348959)

Utilizator CheeseEaterHackRoman Alex CheeseEaterHack Data 24 martie 2026 20:16:02
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.82 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const long long mod1=1000000007;
const long long mod2=1000000009;
const long long baza=911382323;
/*
Rabin-Karp:
facem hash pentru pattern si pentru fiecare fereastra din text
de aceeasi lungime.

Daca hash-urile sunt egale, avem match posibil.

Cand mutam fereastra cu o pozitie:
- scoatem primul caracter din hash
- inmultim cu baza
- adaugam noul caracter

Astfel obtinem hash-ul noii ferestre in O(1),
deci tot algoritmul devine O(n).
*/
int main()
{
    string a, b;
    fin>>a>>b;
    int n=a.size();
    int m=b.size();
    if (n>m)
    {
        fout<<0;
        return 0;
    }
    long long hashA1=0, hashA2=0, hashB1=0, hashB2=0;
    long long pow1=1, pow2=1;
    for (int i=0; i<n; i++)
    {
        hashA1=(hashA1*baza+a[i])%mod1;
        hashA2=(hashA2*baza+a[i])%mod2;

        hashB1=(hashB1*baza+b[i])%mod1;
        hashB2=(hashB2*baza+b[i])%mod2;
        if (i<n-1)
        {
            pow1=pow1*baza%mod1;
            pow2=pow2*baza%mod2;
        }
    }
    vector<int> rez;
    int cnt=0;
    if (hashA1==hashB1 and hashA2==hashB2)
    {
        cnt++;
        rez.push_back(0);
    }
    for (int i=n; i<m; i++)
    {
        hashB1=(hashB1-b[i-n]*pow1%mod1+mod1)%mod1;
        hashB1=hashB1*baza%mod1;
        hashB1=(hashB1+b[i])%mod1;

        hashB2=(hashB2-b[i-n]*pow2%mod2+mod2)%mod2;
        hashB2=hashB2*baza%mod2;
        hashB2=(hashB2+b[i])%mod2;

        if (hashA1==hashB1 and hashA2==hashB2)
        {
            cnt++;
            if (rez.size()<1000)
            {
                rez.push_back(i-n+1);
            }
        }
    }
    fout<<cnt<<'\n';
    for (auto u:rez)
    {
        fout<<u<<" ";
    }

    return 0;
}