[UVa] 12206 - Stammering Aliens

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12206 - Stammering Aliens
Source            : UVA Online Judge
Category          : String, Data Structure
Algorithm         : Suffix Array, Segment Tree
Verdict           : Accepted


#include "bits/stdc++.h"  
  
using namespace std;  
  
#define FAST             ios_base::sync_with_stdio(false), cin.tie(nullptr);  
  
static const int maxn = 40000 + 5;  
static const int logn = 18;  
static const int inf = 12345678;  
  
struct entry  
{  
      int first, second;  
      int p;  
      entry(int ff = 0, int ss = 0, int pp = 0) : first(ff), second(ss), p(pp) {}  
      friend bool operator < (const entry &A, const entry &B)  
      {  
            if (A.first == B.first) return A.second < B.second;  
            return A.first < B.first;  
      }  
} L[maxn];  
  
int P[logn][maxn], B[maxn];  
int p, q;  
int step, lcp[maxn];  
  
inline int comp2(const int &a, const int &b)  
{  
      return P[step-1][a] < P[step-1][b];  
}  
  
inline void suffixArray(const string &s)  
{  
      int len = s.size();  
      for (int i = 0; i < len; i++) P[0][i] = s[i] - 'a';  
      step = 1;  
      int cnt = 1;  
      for ( ; cnt>>1 < len; step++, cnt <<= 1)  
      {  
            for (int i = 0; i < len; i++)  
            {  
                  L[i].first = P[step-1][i];  
                  L[i].second = (i + cnt) < len ? P[step-1][i+cnt] : -1;  
                  L[i].p = i;  
            }  
            sort(L, L+len);  
            for (int i = 0; i < len; i++)  
            {  
                  if (i > 0 && L[i].first == L[i-1].first && L[i].second == L[i-1].second)  
                        P[step][ L[i].p ] = P[step][ L[i-1].p ];  
                  else  
                        P[step][ L[i].p ] = i;  
            }  
      }  
      for (int i = 0; i < len; i++) B[i] = i;  
      sort(B, B+len, comp2);  
}  
  
inline void LCP(const string &s)  
{  
      int len = s.size();  
      memset(lcp, 0, sizeof lcp);  
      for (int i = 1; i < len; i++)  
      {  
            int x = B[i];  
            int y = B[i-1];  
            for (int k = step-1; k >= 0 && x < len && y < len; k--)  
            {  
                  if (P[k][x] == P[k][y])  
                  {  
                        lcp[i] += (1 << k);  
                        x += (1 << k);  
                        y += (1 << k);  
                  }  
            }  
      }  
}  
  
struct segmentTree  
{  
      int len, pos;  
      segmentTree(int len = inf, int pos = 0) : len(len), pos(pos) {}  
  
      inline void assignLeaf(int l, int p)  
      {  
            len = l;  
            pos = p;  
      }  
      inline void marge(const segmentTree &lft, const segmentTree &rgt)  
      {  
            len = min(lft.len, rgt.len);  
            pos = max(lft.pos, rgt.pos);  
      }  
} Tree[maxn << 2];  
  
inline void build(int node, int a, int b)  
{  
      if (a == b)  
      {  
            Tree[node].assignLeaf(lcp[a], B[a]);  
            return;  
      }  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      build(lft, a, mid);  
      build(rgt, mid+1, b);  
      Tree[node].marge(Tree[lft], Tree[rgt]);  
}  
  
inline segmentTree query(int node, int a, int b, int i, int j)  
{  
      if (a == i && b == j) return Tree[node];  
      int lft = node << 1;  
      int rgt = lft | 1;  
      int mid = (a + b) >> 1;  
      segmentTree res = segmentTree();  
      if (j <= mid)  
      {  
            segmentTree p = query(lft, a, mid, i, j);  
            res.marge(res, p);  
      }  
      else if (i > mid)  
      {  
            segmentTree q = query(rgt, mid+1, b, i, j);  
            res.marge(res, q);  
      }  
      else  
      {  
            segmentTree p = query(lft, a, mid, i, mid);  
            segmentTree q = query(rgt, mid+1, b, mid+1, j);  
            res.marge(res, p);  
            res.marge(res, q);  
      }  
      return res;  
}  
  
int main()  
{  
      FAST;  
  
      int m;  
      while (cin >> m)  
      {  
            if (m == 0) break;  
            string s;  
            cin >> s;  
            int len = s.size();  
            if (m == 1)  
            {  
                  cout << len << " " << 0 << endl;  
                  continue;  
            }  
            suffixArray(s);  
            LCP(s);  
            int maxlen = 0;  
            int pos = 0;  
  
            build(1, 0, len-1);  
  
            for (int i = 1; i+m-2 < len; i++)  
            {  
                  if (i+m-2 < 0) continue;  
                  segmentTree res = query(1, 0, len-1, i, i+m-2);  
                  if (res.len > 0)  
                  {  
                        res.pos = max(res.pos, B[i-1]);  
                        if (res.len > maxlen) maxlen = res.len, pos = res.pos;  
                        else if (res.len == maxlen && res.pos > pos) pos = res.pos;  
                  }  
            }  
            if (maxlen == 0) cout << "none" << endl;  
            else cout << maxlen << " " << pos << endl;  
      }  
}