Cod sursa(job #3358245)

Utilizator Dariuscriss72Popescu Darius Mihai Dariuscriss72 Data 15 iunie 2026 19:58:33
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 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)+mod)%mod;
    }
    for(i=0;i<ex1.length();i++){
        ex=(((ex*baza+(ex1[i]-'a'+1))%mod)+mod)%mod;
    }
    i=0;
    if(hash==ex){
            if(s.substr(i,size)==ex1){
                ct++;
                if(ct<1001){
                cont.push_back(i);
                }
            }
    }
    for(i=1;i<=n-size;i++){
        hash=(((hash-put*(s[i-1]-'a'+1))%mod)+mod)%mod;
        hash=(((hash*baza+(s[i+size-1]-'a'+1))%mod)+mod)%mod;
        if(hash==ex){
            if(s.substr(i,size)==ex1){
                ct++;
                if(ct<1000){
                cont.push_back(i);
                }
            }
        }
    }
    
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    f.tie(NULL);
    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;
}