Cod sursa(job #2963651)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 11 ianuarie 2023 19:27:16
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char tx[2000005];
char pat[2000005];

vector <int> sol;

int hv_txt(int p1,int p2)
{
    long long s=0;
    for(int i=p1;i<=p2;i++)
    {
        s+=tx[i];
    }
    return s%INT_MAX;
}
int hv_pat(int p1,int p2)
{
    long long s=0;
    for(int i=p1;i<=p2;i++)
    {
       s+=pat[i];
    }
    return s%INT_MAX;
}
int main()
{
    fin>>pat;
    fin>>tx;
    int tx_last = strlen(tx)-1;
    int pat_last = strlen(pat)-1;
    int patvalue = hv_pat(0,pat_last);
    int txtvalue = hv_txt(0,pat_last-1);
    for(int last = pat_last;last<=tx_last;last++)
    {
        txtvalue+=hv_txt(last,last);

        if(txtvalue==patvalue && tx[last]==pat[pat_last])
        {
            bool ok = true;
            for(int i=0;i<=pat_last;i++)
            {
                if(pat[i]!=tx[last-pat_last+i])
                {
                    ok=false;
                    break;
                }
            }
            if(ok)
            {
                sol.push_back(last-pat_last);
            }
        }

        txtvalue-=hv_txt(last-pat_last,last-pat_last);
    }
    fout<<sol.size()<<'\n';
    for(int i=0;i<min(1000,int(sol.size()));i++)
    {
        fout<<sol[i]<<' ';
    }
}