\(S\) の \(i\) 文字目から始まる接尾辞と \(j\) 文字目から始まる接尾辞の最長共通接頭辞の長さを \(\mathrm{LCP}(i, j)\) と書きます。（\(i, j\) が \([1, N]\) の範囲外の場合の値は \(0\) としておきます。）

\(S\) から取り出す \(2\) つの部分文字列がそれぞれ \(S\) の \(i\) 文字目、\(j\) 文字目から始まる場合の答えを考えます。これは、\(\mathrm{LCP}(i, j)\) がわかれば求められます。具体的には、\(i < j\) のとき \(\min(\mathrm{LCP}(i, j), j - i)\) となります。

そこで、すべての \((i, j)\) について \(\mathrm{LCP}(i, j)\) を求められればよいです。

文字列アルゴリズムを用いる方法もありますが、DP を用いるとより簡単に実装できます。

\(\mathrm{LCP}(i, j)\) は、

• \(S_i \neq S_j\) のとき、\(0\)
• \(S_i = S_j\) のとき、\(1 + \mathrm{LCP}(i + 1, j + 1)\)

となります。そのため、後ろから（\(i, j\) の大きいほうから）\(\mathrm{LCP}(i, j)\) を求めていくことができます。

時間計算量は \(O(N^2)\) です。

C++ による実装例：

#include <bits/stdc++.h>
using namespace std;

int main()
{
  int N;
  string S;
  cin >> N >> S;

  vector lcp(N + 1, vector(N + 1, 0));
  for (int i = N - 1; i >= 0; i--)
  {
    for (int j = N - 1; j >= 0; j--)
    {
      if (S[i] == S[j])
        lcp[i][j] = 1 + lcp[i + 1][j + 1];
    }
  }

  int ans = 0;
  for (int i = 0; i < N; i++)
  {
    for (int j = i + 1; j < N; j++)
    {
      int tmp = min(lcp[i][j], j - i);
      if (ans < tmp)
        ans = tmp;
    }
  }
  cout << ans << endl;
}