SPOJ 694 Distinct Substrings

Description

Given a string, we need to find the total number of its distinct substrings.

Input

T- number of test cases. T<=20;

Each test case consists of one string, whose length is <= 1000

Output

For each test case output one number saying the number of distinct substrings.

Example

Sample Input:

2

CCCCC

ABABA

Sample Output:

5

9

Explanation for the testcase with string ABABA: 

len=1 : A,B

len=2 : AB,BA

len=3 : ABA,BAB

len=4 : ABAB,BABA

len=5 : ABABA

Thus, total number of distinct substrings is 9.

#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Min = 0;
const int Max = 0x7FFFFFFF;
const int maxn = 20005;
const int bit = 1000005;
class suffix
{
private:
  char s[maxn];
  int r[maxn], w[bit], ss[maxn], h[maxn];
  int sa[maxn], rk[maxn + maxn], size;
  int limit;
public:
  bool get(){
    if (scanf("%s", s + 1) != 1) return false;
    size = strlen(s + 1);
    return true;
  }
  void pre()
  {
    memset(rk, 0, sizeof(rk));
    for (int i = 1; i <= bit; i++) w[i] = 0;
    for (int i = 1; i <= size; i++) w[(int)s[i]]++;
    for (int i = 1; i <= bit; i++) w[i] += w[i - 1];
    for (int i = size; i; i--) sa[w[(int)s[i]]--] = i;
    for (int i = 1, j = 1; i <= size; i++)
      rk[sa[i]] = (s[sa[i]] == s[sa[i + 1]] ? j : j++);
    for (int j = 1; j < size; j += j)
    {
      for (int i = 1; i <= size; i++) w[i] = 0;
      for (int i = 1; i <= size; i++) w[rk[i + j]]++;
      for (int i = 1; i <= size; i++) w[i] += w[i - 1];
      for (int i = size; i; i--) ss[w[rk[i + j]]--] = i;

      for (int i = 1; i <= size; i++) w[i] = 0;
      for (int i = 1; i <= size; i++) w[rk[ss[i]]]++;
      for (int i = 1; i <= size; i++) w[i] += w[i - 1];
      for (int i = size; i; i--) sa[w[rk[ss[i]]]--] = ss[i];

      for (int i = 1, k = 1; i <= size; i++)
        r[sa[i]] = (rk[sa[i]] == rk[sa[i + 1]] && rk[sa[i] + j] == rk[sa[i + 1] + j]) ? k : k++;
      for (int i = 1; i <= size; i++) rk[i] = r[i];
    }
    for (int i = 1, k = 0, j; i <= size; h[rk[i++]] = k)
    for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
  }
  void work()
  {
    int ans = 0;
    for (int i = 1; i <= size; i++)
      ans += size - sa[i] + 1 - h[i];
    printf("%d\n", ans);
  }
}f;

int main()
{
  int T;
  scanf("%d", &T);
  while (T--)
  {
    f.get();
    f.pre();
    f.work();
  }
  return 0;
}