Minimalne słowo pokrywające

RNO-Wiki

Niebawem pojawi się tu opis problemu.

Implementacja w języku C++

W poniższej funkcji, argument pi oznacza wektor - funkcję prefiksową Knutha

// pi - funkcja prefiksowa Knutha (indeksowana od 0)
int min_cover_word(const string &u, const vector<int> &pi)
{
  int n = u.length(); if (n==1) return 1;
  int S[n], Z[n];
  for (int i=1; i<n; i++) Z[i]=S[i]=i+1;
  for (int i=1; i<n; i++)
    if (pi[i]>0 && i-Z[S[pi[i]]]<S[pi[i]])
    {
      S[i] = S[pi[i]];
      Z[S[i]] = i;
    }
  return S[n-1];
}