Cod sursa(job #3292641)

Utilizator parrot279Sofi Tudose parrot279 Data 8 aprilie 2025 20:28:54
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

string a, b, sir;
int z[4000002];

int main()
{
    vector<int> rez;
    cin>>a>>b;
    sir = a;
    sir += "$";
    sir += b;
    int n = sir.size(), best = 0, nrsecv = 0;
    int la = a.size();
    z[0] = 0;

    for(int i = 1; i < n; ++i)
    {
        int capatdr = best + z[best];
        int j = i - best;
        if(i < capatdr)
            z[i] = min(z[j], capatdr - i);

        while(i + z[i] < n && sir[z[i]] == sir[i + z[i]])
        {
            z[i]++;
        }
        if(i + z[i] > capatdr)
            best = i;
        if(z[i] == la)
        {
            ++nrsecv;
            if(nrsecv <= 1000)
            {
                rez.push_back(i);
            }
        }
    }
    cout<<nrsecv<<"\n";
    for(auto i : rez)
    {
        cout<<i - la - 1<<" ";
    }

    return 0;
}