UVa1223

UVa1223

LCPを見るだけ。
接尾辞配列の構築みたいなことをする。

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

const int S = 5000 + 1;
char s[S];

bool cmp(int a, int b)
{
  return strcmp(s + a, s + b) < 0;
}

int main(void)
{
  int idx[S];

  int tc; 
  cin >> tc;
  while (tc--) {
    cin >> s;
    int size = strlen(s);
    s[size++] = '$';
    for (int i = 0; i < size; ++i) {
      idx[i] = i;
    }
    sort(idx, idx + size, cmp);

//     for (int i = 0; i < size; ++i) {
//       cout << (s + idx[i]) << endl;
//     }

    int mx = 0;
    for (int i = 0; i+1 < size; ++i) {
      int cnt = 0;
      while (s[idx[i] + cnt] == s[idx[i + 1] + cnt]) ++cnt;
      mx = max(mx, cnt);
    }
    cout << mx << endl;
  }
  return 0;
}