Ən böyük sərhəd (Həll təhlili)

$S$ sətri üçün $p$ massivində prefiks-funksiyanı quracağıq. Əgər $S$ sətrinin uzunluğu $n$-dirsə, onda problemi həll etmək üçün sadəcə p[n - 1] dəyərini qaytarmaq kifayətdir.

Alqoritmin realizasiyası

Daxil olan sətir $s$ üçün prefiks-funksiyanı $p$ massivində qururuq.

string s;
vector<int> p;

MaxBorderArray funksiyası $s$ sətri üçün prefiks-funksiyanı hesablayır.

vector<int> MaxBorderArray(string &s)
{
  vector<int> p(s.size()); // p[0] = 0
  for (int i = 1; i < s.size(); i++)
  {
    int j = p[i - 1];
    while ((j > 0) && (s[i] != s[j])) 
      j = p[j - 1];
    if (s[i] == s[j]) p[i] = j + 1; else p[i] = 0;
  }
  return p;
}

$s$ sətri üçün prefiks-funksiyanı MaxBorderArray funksiyası ilə qururuq.

cin >> s;
p = MaxBorderArray(s);

Sətirin ən uzun sərhədinin uzunluğunu qaytarırıq, bu p[s.size() - 1]-də yerləşir.

printf("%d\n", p[s.size() - 1]);