Cod sursa(job #3214257)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 13 martie 2024 22:52:17
Problema Potrivirea sirurilor Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

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

string A , B;
int z[4000005] , ans;
vector <int> v;

void ZFunction ()
{
    int L = 0 , R = 0;
    A = B + "$" + A;
    for (int i = 0; i < (int)A.size(); ++i)
    {
        z[i] = min(R - i , z[i - L]);
        while(i + z[i] < A.size() && A[z[i]] == A[i + z[i]])
            ++z[i];
        if(i + z[i] > R)
            L = i , R = i + z[i];
    }
    for (int i = 0; i < A.size(); ++i)
    {
        ans += (z[i] == B.size());
        if(v.size() < 1000 && z[i] == B.size())
            v.push_back(i - B.size() - 1);
    }
    fout << ans << "\n";
    for (auto x : v)
        fout << x << " ";
}

int main()
{
    fin >> B >> A;
    ZFunction();
}