Cod sursa(job #3192971)

Utilizator Simon2712Simon Slanina Simon2712 Data 13 ianuarie 2024 17:07:41
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=2e6;
const int MOD=1e9+2727;
char a[N],b[N];
int hashh[N];
int v[1001];
int cif(char ch)
{
    if('a'<=ch && ch<='z')
        return ch-'a'+1;
    if('A'<=ch && ch<='Z')
        return ch-'A'+27;
    return ch-'0'+53;
}
int main()
{
    int cod=0,baza=63,asize,bsize,put,i,cnt,val;
    fin>>a>>b;
    asize=strlen(a);
    bsize=strlen(b);
    put=1;
    for(i=0;i<asize;i++){
        cod=(1LL*cod*baza+cif(a[i]))%MOD;
        put=(1LL*put*baza)%MOD;
    }
    hashh[0]=cif(b[0]);
    for(i=1;i<bsize;i++)
        hashh[i]=(1LL*hashh[i-1]*baza+cif(b[i]))%MOD;
    cnt=0;
    if(hashh[asize-1]==cod)
    {
        cnt++;
        v[cnt]=0;
    }
    for(i=asize;i<bsize;i++)
    {
        val=hashh[i]-(1LL*hashh[i-asize]*put)%MOD;
        if(val<0)
            val+=MOD;
        if(val==cod)
        {
            cnt++;
            if(cnt<=1000)
                v[cnt]=i-asize+1;
        }
    }
    fout<<cnt<<'\n';
    for(i=1;i<=cnt;i++)
        fout<<v[i]<<" ";
    return 0;
}