Cod sursa(job #3359556)

Utilizator radu_flradu fl radu_fl Data 30 iunie 2026 11:39:03
Problema Potrivirea sirurilor Scor 24
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb

#include <bits/stdc++.h>
using namespace std;
const long long base=27;
const long long mod=1e9+7;
const int nmax=2e6+5;
long long coda[nmax],codb[nmax],p[nmax];
int sol[nmax];
void encode(string s,long long cod[]){
    int n=s.size();
    cod[0]=s[0]-'a';
    for(int i=1;i<n;i++){
        cod[i]=(base*cod[i-1]%mod+(s[i]-'a'))%mod;
    }
}
int main(){
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string a,b;
    fin>>a>>b;
    int n=a.size(),m=b.size();
    encode(a,coda);
    encode(b,codb);
    p[0]=1;
    for(int i=1;i<=m;i++)
        p[i]=p[i-1]*base%mod;
    long long hasha=coda[n-1];
    int cnt=0;
    for(int st=0;st+n-1<m;st++){
        int dr=st+n-1;
        long long hashc;
        if(st==0){
            hashc=codb[dr];
        }
        else 
            hashc=(codb[dr]-codb[st-1]*p[n]%mod+mod)%mod;
            if(hashc==hasha){
                sol[cnt]=st;
                cnt++;
            }
    }
    fout<<cnt<<'\n';
    for(int i=0;i<cnt;i++){
        fout<<sol[i]<<" ";
    }
    return 0;
}