aslan7470

Идея:
Берем N последовательностей длины 1, начинающиеся в элементах 0..N-1, выписываем в массив позицию их 1го символа (0..N-1), сортируем по символу в этой позиции. Для групп с одинаковым символом вызываем рекурсивно, рассматривая 2й символ с позиции, записанной в массиве итд

Псевдокод:

find(N,A[])
  p[N]={0..N-1} // позиции начала подстрок
  l=0,ml=0,s // длина, макс длина подстроки, позиция подстроки макс длины
  finda(0,N)

// искать среди позиций p[i..j-1]  
def finda(i,j)
  if l>ml && j-i>1
    ml=l
    s=p[i]
  ++l
  // оставим в p[i..j-1] позиции <= N-l
  m=j,k=j=i
  while k<m
    if p[k]<=N-l
      p[j++]=p[k]
    ++k
  sort p[i..j-1]):A[p[i]+l]
  k=m=i
  while ++k<j
    if(A[p[k]+l]!=A[p[k-1]+l]) // конец группы подстрок с равным символом на позиции l от начала
      finda(m,k)
      m=k
  finda(m,j) // последняя группа подстрок с равным символом на позиции l от начала
  --l