Distinct Substrings SPOJ – DISUBSTR

Distinct Substrings

求不同子串个数.
对排好序的后缀,相邻两个后缀产生的不同子串数为:
(n-sa[i])+(n-sa[i-1])-height[i].

而(n-sa[i])+(n-sa[i-1])的累加就是(n+1)*n/2

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <utility>
using namespace std;
const int INF = 1e9;
const int MAX_V = 10005;
const int MAX_E= 200005;

int c[20010],_rank[20010],temp[20010],sa[20010],height[20010];
void da(int str[],int n,int m){
  n++;
  int i,j,p;
  for(i=0;i<m;++i) c[i]=0;
  for(i=0;i<n;++i) c[_rank[i]=str[i]]++;
  for(i=1;i<m;++i) c[i]+=c[i-1];
  for(i=n-1;i>=0;--i) sa[--c[_rank[i]]]=i;
  for(j=1;j<=n;j<<=1){
    p=0;
    //若未对str进行离散化,第一轮rank不是真正的rank,是大小关系相对确定的rank.
    //_rank[i]为上一轮第i个位置的rank(也是此轮第i个位置的第一关键字, 第i-j个位置的第二关键字)
    //temp[i]为第i小的第二关键字对应的串首位置(第一关键字的下标)
    for(i=n-j;i<n;++i) temp[p++]=i; //无第二关键字
    for(i=0;i<n;++i){
      if(sa[i]>=j) temp[p++]=sa[i]-j;
    }
    //排序第一关键字_rank[i],当_rank[i]相等时,让第二关键字小的排前面
    for(i=0;i<m;++i) c[i]=0;
    for(i=0;i<n;++i) c[_rank[temp[i]]]++;
    for(i=1;i<m;++i) c[i]+=c[i-1];
    for(i=n-1;i>=0;--i) sa[--c[_rank[temp[i]]]] = temp[i];
    //新的rank数组要由老的rank数组得到,因而将rank转移到temp上
    swap(_rank,temp);
    p=1;
    _rank[sa[0]]=0;
    for(i=1;i<n;++i){
      _rank[sa[i]]=temp[sa[i-1]]==temp[sa[i]]&&temp[sa[i-1]+j]==temp[sa[i]+j]?p-1:p++;
    }
    if(p>=n) break;
    m=p;
  }

  int k=0;
  n--;

  //height[rank[i]]>=height[rank[i-1]]-1
  for(i=0;i<n;++i){
    if(k) k--;
    j=sa[_rank[i]-1];
    while(str[i+k]==str[j+k]) k++;
    height[_rank[i]]=k;
  }

}

char s[1005];
int t[1005];
int main(){
  int T;
  cin>>T;
  while(T--){
    scanf("%s",s);
    int len=strlen(s);
    int m=0;
    for(int i=0;i<len;++i){
       t[i]=s[i]-0;
       m=max(s[i]-0,m);
    }
    t[len]=0;
    da(t,len,m+1);
    int ans=len*(len+1)/2;
    for(int i=0;i<=len;++i){
        ans-=height[i];
       // cout<<height[i]<<endl;
    }
    printf("%d\n",ans);
  }

}

发表评论

电子邮件地址不会被公开。 必填项已用*标注