Cod sursa(job #2732609)

Utilizator CatalinPangaleanuCatalin Pangaleanu CatalinPangaleanu Data 29 martie 2021 07:45:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

int lps[2000001];

inline void getLPS(const string& a)
{   int j, i;
    j=0;
    for (i=1;i<a.size();)
        if (a[i]==a[j])
        {   ++j;
            lps[i]=j;
            ++i;
        }
        else
            if (j)
                j=lps[j-1];
            else
                ++i;
}

inline void getMatches(const string& a, const string& b)
{   vector<int> pos;
    int cnt, i, j;
    cnt=0;
    pos.reserve(1000);
    for (i=j=0;i<b.size();)
    {   if (a[j]==b[i])
            ++i, ++j;
        else
            if (j)
                j=lps[j-1];
            else
                ++i;
        if (j==a.size())
        {   ++cnt;
            if (pos.size()<1000)
                pos.push_back(i-j);
            j=lps[j-1];
        }
    }
    fout<<cnt<<'\n';
    for (i=0;i<pos.size();++i)
        fout<<pos[i]<<' ';
}

int main()
{   ios::sync_with_stdio(false);
    fin.tie(nullptr), fout.tie(nullptr);
    string a, b;
    fin>>a>>b;
    fin.close();
    getLPS(a);
    getMatches(a, b);
    fout.close();

    return 0;
}