Cod sursa(job #3038696)

Utilizator TraianQTraianQ TraianQ Data 27 martie 2023 17:53:24
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <string>
using namespace std;
int v[2000005];
int main()
{
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    string a,b;
    long long codA=0,codB=0,cnt=0,put=1;
    cin>>a>>b;
    if(b.size()<a.size())
    {
        cout<<0;
        return 0;
    }
    for(int i=0;i<a.size();i++)
    {
        codA=(1LL*codA*128+a[i])%1000000000000;
        codB=(1LL*codB*128+b[i])%1000000000000;
        put=(1LL*put*128)%1000000000000;
    }
    if(codA==codB)
    {
        cnt++;
        v[cnt]=0;
    }
    for(int i=a.size();i<b.size();i++)
    {
        codB=(long long)((1LL*codB*128+b[i])%1000000000000);
        codB=(long long)((codB-b[i-a.size()]*put)%1000000000000);
        if(codB<0)
            codB+=1000000000000;
        if(codB==codA)
        {
            cnt++;
            v[cnt]=i-a.size()+1;
        }
    }
    cout<<cnt<<'\n';
    for(int i=1;i<=min(cnt,1000LL);i++)
        cout<<v[i]<<" ";
    return 0;
}