刷题记（后缀数组 I） —— 2018.5.3

最长公共子串、至少重复K次最长子串、不重复子串

Update(2019.07.09)

修改了模板，并加入更详细的注释

前言

之前啃到Trie树的时候想啃后缀树，然后发现这个东西普通思想需要O(n^2)，而优化思想可以线性时间但是听说很麻烦，于是乎就用后缀数组来代替后缀树
啃的时候觉得后缀数组很难，啃完后发现它是高级算法……
还没啃的部分有朝一日再啃吧
另外注意，本文使用的是倍增算法(O(nlogn))，DC3算法(O(n))还没啃……

Longest Common Substring - HDU 1403

题目大意
求两个串的最长公共子串

思路
将一个串接到另一个串后面，中间用别的字符分割开，然后求sa、rank、height数组，那么最长公共子串就是height数组中满足sa[i]和sa[i - 1]分别位于两个串条件的最大值

#include <bits/stdc++.h>
using namespace std;
const int N = (int)200000 + 15;

int t1[N], t2[N], buc[N], sa[N], rk[N], height[N];
char s[N];

// buc：桶
// sa[i]：第i名是第sa[i]个字符串，即sa形成了后缀排序后的数组
// rank[i]：第i个字符串排第rank[i]名 (rank = rk)
// height[i]：第sa[i]与第sa[i-1]个字符串的LCP值，即height[i] = lcp(sa[i], sa[i-1])

inline void buildSA(char* s, int n, int m = 128) {
    int* x = t1, *y = t2;
    memset(buc + 1, 0, m * sizeof(int));
    //使用基数排序获得初始排序值
    //x[i]：第i个的排名是x[i]
    for(int i = 1; i <= n; i++) {
        buc[x[i] = s[i]]++;
    }
    for(int i = 1; i <= m; i++) {
        buc[i] += buc[i - 1];
    }
    for(int i = n; i >= 1; i--) {
        sa[buc[x[i]]--] = i;
    }

    for(int k = 1; k <= n; k <<= 1) {
        //y[i]：第i名是第y[i]个，属于次要关键字
        //由于后面k个都没有次要关键字，所以都是第1名
        //上一层的前面k个不能转移
        //由于y[i]是按名次的，所以以遍历sa的顺序放入
        int p = 0;
        for(int i = n - k + 1; i <= n; i++) {
            y[++p] = i;
        }
        for(int i = 1; i <= n; i++) {
            if(sa[i] > k) {
                y[++p] = sa[i] - k;
            }
        }
        //基数排序获取两个关键字合并后的sa
        //基数排序是从低位往高位的，原理（可能？）为其是稳定排序
        //因此下方同一个桶的值按y[i]的顺序
        memset(buc + 1, 0, m * sizeof(int));
        for(int i = 1; i <= n; i++) {
            buc[x[i]]++;
        }
        for(int i = 1; i <= m; i++) {
            buc[i] += buc[i - 1];
        }
        for(int i = n; i >= 1; i--) {
            sa[buc[x[y[i]]]--] = y[i];
        }
        //如果相邻排名的主要关键字排名相同，且次要关键字排名也相同
        //那么合并后排名也相同，还需要进一步倍增
        //如果都不相同，那么说明已经排序完成，可以退出算法
        swap(x, y);
        p = x[sa[1]] = 1;
        for(int i = 2; i <= n; i++) {
            int a = sa[i] + k > n ? -1 : y[sa[i] + k];
            int b = sa[i - 1] + k > n ? -1 : y[sa[i - 1] + k];
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && a == b) ? p : ++p;
        }
        if(p >= n) {
            break;
        }
        m = p;
    }
}

inline void getHeight(char* s, int n) {
    //rk[sa[i]] == i是显然的
    for(int i = 1; i <= n; i++) {
        rk[sa[i]] = i;
    }
    //h[i]=height[rank[i]]=lcp(sa[rank[i]], sa[rank[i]-1])=lcp(i,sa[rank[i]-1])
    //有性质h[i]>=h[i-1]+1
    int k = 0;
    for(int i = 1; i <= n; i++) {
        if(rk[i] == 1) {
            continue;
        }
        //利用性质h[i]>=h[i-1]+1
        if(k) {
            k--;
        }
        int j = sa[rk[i] - 1];
        while(s[i + k] == s[j + k]) {
            k++;
        }
        height[rk[i]] = k;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    while(cin >> (s + 1)) {
        int pos = strlen(s + 1) + 1;
        s[pos] = '$';
        cin >> (s + 1 + pos);
        int n = strlen(s + 1);
        buildSA(s, n);
        getHeight(s, n);

        int maxx = 0;
        for(int i = 2; i <= n; i++) {
            if(maxx < height[i] && (sa[i - 1] < pos && sa[i] > pos || sa[i - 1] > pos && sa[i] < pos)) {
                maxx = height[i];
            }
        }
        cout << maxx << "\n";
    }
    cout.flush();
}

Milk Patterns - POJ 3261

题目大意
求至少重复K次的最长子串

思路
二分答案，二分时对height数组分组求即可（说得好像很简单的样子）

  #include<cstdio>
  #include<iostream>
  #include<cstring>
  using namespace std;
  const int N = 1000000 + 15;
  int s[N];
  int sa[N], t1[N], t2[N], buc[N];
  int rk[N], height[N];

  void buildSA(int n,int m){
      int* x = t1;
      int* y = t2;
      for(int i = 0; i < m; i++)          buc[i] = 0;
      for(int i = 0; i < n; i++)          buc[x[i] = s[i]]++;
      for(int i = 1; i < m; i++)          buc[i] += buc[i-1];
      for(int i = n - 1; i >= 0; i--)     sa[--buc[x[i]]] = i;

      for(int j = 1, p = 0; j <= n; j <<= 1, p = 0){
          for(int i = n - j; i < n; i++)   y[p++] = i;
          for(int i = 0; i < n; i++){
              if(sa[i]>=j)   y[p++] = sa[i] - j;
          }

          for(int i = 0; i < m; i++)          buc[i] = 0;
          for(int i = 0; i < n; i++)          buc[x[y[i]]]++;
          for(int i = 1; i < m; i++)          buc[i] += buc[i-1];
          for(int i = n - 1; i >= 0; i--)     sa[--buc[x[y[i]]]] = y[i];

          swap(x, y);
          p = 1; x[sa[0]] = 0;
          for(int i = 1; i < n; i++)
              x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j] ? p - 1 : p++);
          if(p >= n)    break;
          m = p;
      }
  }

  void getHeight(int n){
      for(int i = 1; i <= n; i++)     rk[sa[i]] = i;
      for(int i = 0, k = 0; i < n; i++){
          if(k)   k--;
          int j = sa[rk[i] - 1];
          while(s[i + k] == s[j + k]) k++;
          height[rk[i]] = k;
      }
  }

  int getMaxCnt(int n, int len){
      int ans = 0;
      int cnt = 0;
      for(int i = 2; i <= n; i++){
          if(height[i] >= len){
              cnt++;
              ans = max(ans, cnt);
          }else{
              cnt = 0;
          }
      }
      return ans;
  }

  int main(){
      int n, k;
      while(~scanf("%d%d", &n, &k)){
          for(int i = 0; i < n; i++){
              scanf("%d", &s[i]);
              s[i]++;
          }
          s[n] = 0;
          buildSA(n + 1, 1000000 + 5);
          getHeight(n);

          int l = 0;
          int r = n;
          while(l < r){
              int mid = (l + r + 1) >> 1;
              if(getMaxCnt(n, mid) + 1 >= k){
                  l = mid;
              }else{
                  r = mid - 1;
              }
          }
          printf("%d\n", l);
      }
  }

New Distinct Substrings - SPOJ-SUBST1

题目大意
求一个串中有多少不重复子串

思路
每个子串都是后缀的某个前缀，因此重复的子串必然是某两个串的LCP的所有前缀（包括LCP）
要求有多少不重复子串，就是求所有子串 - 重复子串，重复子串数等于height数组之和（画图可知）

  #include <cstdio>
  #include <iostream>
  #include <cstring>
  #include <cmath>
  #include <algorithm>
  using namespace std;
  const int N = 50000 + 15;
  typedef long long ll;

  char s[N];
  int sa[N], t1[N], t2[N], buc[N];
  int rk[N], height[N];
  int q[N][20];

  void buildSA(int n,int m){
      int* x = t1;
      int* y = t2;
      for(int i = 0; i < m; i++)          buc[i] = 0;
      for(int i = 0; i < n; i++)          buc[x[i] = s[i]]++;
      for(int i = 1; i < m; i++)          buc[i] += buc[i-1];
      for(int i = n - 1; i >= 0; i--)     sa[--buc[x[i]]] = i;

      for(int j = 1, p = 0; j <= n; j <<= 1, p = 0){
          for(int i = n - j; i < n; i++)   y[p++] = i;
          for(int i = 0; i < n; i++){
              if(sa[i]>=j)   y[p++] = sa[i] - j;
          }

          for(int i = 0; i < m; i++)          buc[i] = 0;
          for(int i = 0; i < n; i++)          buc[x[y[i]]]++;
          for(int i = 1; i < m; i++)          buc[i] += buc[i-1];
          for(int i = n - 1; i >= 0; i--)     sa[--buc[x[y[i]]]] = y[i];

          swap(x, y);
          p = 1; x[sa[0]] = 0;
          for(int i = 1; i < n; i++)
              x[sa[i]] = (y[sa[i-1]] == y[sa[i]] && y[sa[i - 1] + j] == y[sa[i] + j] ? p - 1 : p++);
          if(p >= n)    break;
          m = p;
      }
  }

  void getHeight(int n){
      for(int i = 1; i <= n; i++)     rk[sa[i]] = i;
      for(int i = 0, k = 0; i < n; i++){
          if(k)   k--;
          int j = sa[rk[i] - 1];
          while(s[i + k] == s[j + k]) k++;
          height[rk[i]] = k;
      }
  }

  int main(){
      int t;
      scanf("%d", &t);
      while(t--){
          scanf("%s", s);
  		ll len = strlen(s);

  		buildSA(len + 1, 300);
  		getHeight(len);

  		ll ans = (len*(len + 1)) >> 1;
  		for(int i = 2; i <= len; i++)     ans -= height[i];
  		printf("%lld\n", ans);
  	}
  }