[UVa] 12191 - File Recover

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 12191 - File Recover
Source            : UVA Online Judge
Category          : String
Algorithm         : Suffix Array
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define FAST             ios_base::sync_with_stdio(false), cin.tie(nullptr);  
  
#define ll               long long int  
  
static const int maxn = 1e5 + 5;  
static const int logn = 20;  
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] - '0';  
      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);  
                  }  
            }  
      }  
}  
  
  
int main()  
{  
      FAST;  
  
      string s;  
      while (cin >> s)  
      {  
            if (s[0] == '*') break;  
            int len = s.size();  
            suffixArray(s);  
            LCP(s);  
            ll ans = 0;  
            for (int i = 1; i < len; i++)  
            {  
                  if (lcp[i] >= lcp[i-1]) ans += (lcp[i] - lcp[i-1]);  
            }  
            cout << ans << endl;  
      }  
}