Cod sursa(job #3333365)

Utilizator Matei_AndronacheMatei Andronache Matei_Andronache Data 13 ianuarie 2026 10:41:11
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.94 kb
#include <bits/stdc++.h>
#define mod 1000000007
#define baza 131
#define int long long
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int h,H[2000001];
bool ok[2000001];
signed main()
{
    string a,b;
    fin>>a>>b;
    for (int i=0;i<a.size();i++)
    {
      h=(h*baza+a[i])%mod;
      H[0]=(H[0]*baza+b[i])%mod;
    }
    int p=1;
    for (int i=1;i<a.size();i++)
    {
      p=(p*baza)%mod;
    }
    for (int i=1;i<=b.size()-a.size();i++)
    {
      H[i]=((H[i-1]-(b[i-1])*p)*baza+b[i+a.size()-1])%mod;
    }
    int nr=0;
    for (int i=0;i<=b.size()-a.size();i++)
    {
      if (H[i]==h)
      {
        if (a==b.substr(i,a.size()))
        {
          ok[i]=1;
          nr++;
        }
      }
    }
    fout<<nr<<'\n';
    int x=0;
    for (int i=0;i<=b.size()-a.size() && x<=1000;i++)
    {
       if (ok[i]==1)
        fout<<i<<" ";
       x++;
    }
    return 0;
}