Cod sursa(job #3359630)

Utilizator radu_flradu fl radu_fl Data 1 iulie 2026 08:38:37
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
using namespace std;
const int nmax=2000005;
const int base=73;
const int mod1=1000000007;
int coda1[nmax],codb1[nmax],p1[nmax];
int sol[nmax];
void encode(string s, int cod[], int mod){
    int n=s.size();
    cod[0]=(int)s[0];
    for(int i=1;i<n;i++)
        cod[i]=(1LL*base*cod[i-1]+(int)s[i])%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, coda1, mod1);
    encode(b, codb1, mod1);
    p1[0]=1;
    for(int i=1;i<=m;i++)
        p1[i]=1LL*p1[i-1]*base%mod1;
    int hasha1=coda1[n-1];
    int cnt=0;
    for(int st=0;st+n-1<m;st++){
        int dr=st+n-1;
        int hash1;
        if(st==0)
            hash1=codb1[dr];
        else
            hash1=(codb1[dr]-1LL*codb1[st-1]*p1[n]%mod1+mod1)%mod1;
        if(hash1==hasha1){
            sol[cnt]=st;
            cnt++;
        }
    }
    fout<<cnt<<'\n';
    for(int i=0;i<cnt && i<1000;i++)
        fout<<sol[i]<<' ';

    return 0;
}