Cod sursa(job #3358243)

Utilizator Dariuscriss72Popescu Darius Mihai Dariuscriss72 Data 15 iunie 2026 19:47:15
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb

#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int ct=0;
std::vector<int> cont;
int expon(int baza,int n,int m){
    int r=1;
    baza=baza%m;
    while(n>0){
        if(n&1){
            r=((r%m)*(baza%m))%m;
        }
        baza=((baza%m)*(baza%m))%m;
        n/=2;
    }
    return r;
}
void roll(string s,string ex1,int size){
    int n=s.length(),baza=29,mod=1000000007,hash=0,put=expon(baza,size-1,mod),i,ex=0;
    for(i=0;i<size;i++){
        hash=(hash*baza+(s[i]-'a'+1))%mod;
    }
    for(i=0;i<ex1.length();i++){
        ex=(ex*baza+(ex1[i]-'a'+1))%mod;
    }
    i=0;
    if(hash==ex){
            if(s.substr(i,size)==ex1){
                ct++;
                cont.push_back(i);
            }
    }
    for(i=1;i<=n-size;i++){
        hash=(hash-put*(s[i-1]-'a'+1))%mod;
        hash=(hash*baza+(s[i+size-1]-'a'+1))%mod;
        if(hash==ex){
            if(s.substr(i,size)==ex1){
                ct++;
                cont.push_back(i);
            }
        }
    }
    
}
int32_t main()
{
    int m,a,n,i,siz;
    string s,s1;
    f>>s1>>s;
    siz=s1.length();
    roll(s,s1,siz);
    g<<ct<<"\n";
    for(auto i:cont){
        g<<i<<" ";
    }
    return 0;
}