SPOJ 705 New 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 <= 50000

Output

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

Example

Input: 2 CCCCC ABABA Output: 5

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 = 50005;
const int bit = 256;
class suffix
{
private:
  char s[maxn];
  int r[maxn], w[maxn], 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()
  {
    long long ans = 0;
    for (int i = 1; i <= size; i++)
      ans += size - sa[i] + 1 - h[i];
    printf("%lld\n", ans);
  }
}f;

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

#include<set>
#include<map>
#include<ctime>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define fi first
#define se second
#define mp(i,j) make_pair(i,j)
#define pii pair<int,int>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-8;
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const int read()
{
  char ch = getchar();  
  while (ch<'0' || ch>'9') ch = getchar();
  int x = ch - '0';
  while ((ch = getchar()) >= '0'&&ch <= '9') x = x * 10 + ch - '0';
  return x;
}
int T = 0;

struct Sa
{
  char s[N];
  int rk[2][N], sa[N], h[N], w[N], now, n;
  int rmq[N][20], lg[N];

  bool GetS()
  {
    scanf("%s", s + 1);
    return true;
  }

  void getsa(int z, int &m)
  {
    int x = now, y = now ^= 1;
    rep(i, 1, z) rk[y][i] = n - i + 1;
    for (int i = 1, j = z; i <= n; i++)
      if (sa[i] > z) rk[y][++j] = sa[i] - z;

    rep(i, 1, m) w[i] = 0;
    rep(i, 1, n) w[rk[x][rk[y][i]]]++;
    rep(i, 1, m) w[i] += w[i - 1];
    per(i, n, 1) sa[w[rk[x][rk[y][i]]]--] = rk[y][i];
    for (int i = m = 1; i <= n; i++)
    {
      int *a = rk[x] + sa[i], *b = rk[x] + sa[i - 1];
      rk[y][sa[i]] = *a == *b&&*(a + z) == *(b + z) ? m - 1 : m++;
    }
  }

  void getsa(int m)
  {
    n = strlen(s + 1);
    rk[1][0] = now = sa[0] = s[0] = 0;
    rep(i, 1, m) w[i] = 0;
    rep(i, 1, n) w[s[i]]++;
    rep(i, 1, m) rk[1][i] = rk[1][i - 1] + (bool)w[i];
    rep(i, 1, m) w[i] += w[i - 1];
    rep(i, 1, n) rk[0][i] = rk[1][s[i]];
    rep(i, 1, n) sa[w[s[i]]--] = i;

    rk[1][n + 1] = rk[0][n + 1] = 0;  //多组的时候容易出bug
    for (int x = 1, y = rk[1][m]; x <= n && y <= n; x <<= 1) getsa(x, y);
    for (int i = 1, j = 0; i <= n; h[rk[now][i++]] = j ? j-- : j)
    {
      if (rk[now][i] == 1) continue;
      int k = n - max(sa[rk[now][i] - 1], i);
      while (j <= k && s[sa[rk[now][i] - 1] + j] == s[i + j]) ++j;
    }
  }

  void getrmq()
  {
    h[n + 1] = h[1] = lg[1] = 0;
    rep(i, 2, n) rmq[i][0] = h[i], lg[i] = lg[i >> 1] + 1;
    for (int i = 1; (1 << i) <= n; i++)
    {
      rep(j, 2, n)
      {
        if (j + (1 << i) > n + 1) break;
        rmq[j][i] = min(rmq[j][i - 1], rmq[j + (1 << i - 1)][i - 1]);
      }
    }
  }

  int lcp(int x, int y)
  {
    int l = min(rk[now][x], rk[now][y]) + 1, r = max(rk[now][x], rk[now][y]);
    return min(rmq[l][lg[r - l + 1]], rmq[r - (1 << lg[r - l + 1]) + 1][lg[r - l + 1]]);
  }

  void work()
  {
    GetS(); getsa(300);
    LL ans = n - sa[1] + 1;
    rep(i, 2, n) ans += n - sa[i] + 1 - h[i];
    printf("%lld\n", ans);
  }
}sa;

int main()
{
  T = read();
  while (T--) sa.work();
  return 0;
}