Cod sursa(job #3300527)

Utilizator aaagabiTurbinca Gabriel aaagabi Data 16 iunie 2025 22:04:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <fstream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int f[100005];
int g[100005];
int h[100005];
int gs[100005];
int bc[256];
string p;
string t;
int main()
{
    //
    fin>>p>>t;
    for(int i=0;i<256;i++)
        bc[i]=0;
    int m=p.size();
    for(int i=0;i<p.size();i++)
        bc[p[i]]=i;
    f[0]=-1;
    for(int i=1;i<=m;i++)
    {
        int k=f[i-1];
        while(k>=0&&p[i-1]!=p[k])
            k=f[k];
        f[i]=k+1;
    }
    for(int i=0;i<m;i++)
        gs[i]=f[m]-(m-i);
    reverse(p.begin(),p.end());
    h[0]=-1;
    for(int i=1;i<=m;i++)
    {
        int k=h[i-1];
        while(k>=0&&p[i-1]!=p[k])
            k=h[k];
        h[i]=k+1;
    }

    for(int i=0;i<=m;i++)
        g[i]=h[m-i];
    for(int i=0;i<=m;i++)
        gs[m-g[i]]=i;
    int i=0;
    int k=0;
    int n=t.size();
    reverse(p.begin(),p.end());
    int lasti=-1;
    int cnt=0;
    vector <int> ans;
    while(i<=n-m)
    {
        if(t[i+m-k-1]==p[m-k-1])
        {
            k++;
            if(k==m)
            {
                if(ans.size()<1000)
                {
                    ans.push_back(i);
                }
                i+=m-f[m];
                k=0;
            }
        }
        else
        {
            int shiftbc=m-k-1-bc[t[i+m-k-1]];
            int shiftgs=m-k-gs[m-k];
            i+=max(shiftbc,shiftgs);
            k=0;
        }
    }
    fout<<ans.size()<<'\n';
    for(int i:ans)
        fout<<i<<' ';
    /*if(i>n-m)
    {
        cout<<"prst\n";
    }
    else
        cout<<"good\n"<<i<<'\n';
    // kmp*/
    /*
    i=0;
    k=0;
    while(i<=n-m&&k<m)
    {
        if(t[i+k]==p[k])
            k++;
        else
        if(k==0)
            i++;
        else
        {
            i=i+k-f[k];
            k=f[k];
        }
    }
    if(i>n-m)
        cout<<"prstkmp\n";
    else
        cout<<"goodkmp\n"<<i<<' ';*/
    return 0;
}