Найдовший бордюр (Розбір)

Знайдемо для рядка $S$ в масиві $p$ префікс-функцію. Якщо довжина рядка $S$ дорівнює $n$, то для розв’язання задачі достатньо вивести значення p[n - 1].

Реалізація алгоритму

Префікс-функцію вхідного рядка $s$ будуємо в масиві $p$.

string s;
vector<int> p;

Функція MaxBorderArray обчислює префікс-функцію для рядка $s$.

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$ за допомогою функції MaxBorderArray.

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

Виводимо довжину найбільшої границі рядка, яка знаходиться в p[s.size() - 1].

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