Cod sursa(job #2789463)

Utilizator Diana_IonitaIonita Diana Diana_Ionita Data 27 octombrie 2021 16:09:28
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long rasp[1005];

string a,b;
void subsir()
{
    long long nr=0;
    long long n=a.size();
    long long pp,c=0,cod=0,p=1;
    long long mod=100007;

    for(long long i=n-1; i>=0; i--)
    {
        cod+=(a[i]-'A')*p;
        cod%=mod;
        p*=26;
        p%=mod;
        if(i==1)pp=p;

    }
    long long m=b.size();
    p=1;
    if(n>m)
    {
        fout<<0;
        return;
    }
    for(long long i=n-1; i>=0; i--)
    {
        c+=(b[i]-'A')*p;
        cod%=mod;
        p*=26;
        p%=mod;
    }
    if(c==cod)
    {
        long long  i=0;
        while(a[i]==b[i]&&i<n)
        {
            i++;
        }
        if(i==n)
        {
            rasp[++nr]=0;
        }
    }
    for(long long i=n; i<m; i++)
    {
        c-=(b[i-n]-'A')*pp;
        c*=26;
        c%=mod;
        c+=b[i]-'A';
        c%=mod;
        if(c==cod)
        {
            long long   j=0;
            long long k=i-n+1;
            while(a[j]==b[k]&&j<n)
            {
                j++;
                k++;
            }
            if(j==n)
            {
                rasp[++nr]=i-n+1;
                if(nr==1000)break;
            }
        }
    }
    fout<<nr<<'\n';
    for(long long i=1; i<=nr; i++)fout<<rasp[i]<<" ";
}
int main()
{
    fin>>a;
    fin.get();
    fin>>b;
    subsir();
    return 0;
}