题目概述

HDU3518

解题报告

枚举子串的长度 $len$ ，然后将后缀数组按照 $Height\ge len$ 分块，每个块中检查最左和最右的子串是否交叉就行了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ULL;
const int maxn=1000,LOG=17,BA=23333;

int n,ans;char s[maxn+5];
int SA[maxn+5],rk[maxn+5],t[(maxn<<1)+5],ha[maxn+5],H[maxn+5];

void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
void Make(int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i-1]]!=t[SA[i]] || t[SA[i-1]+k]!=t[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++) {if (k) k--;while (s[i+k]==s[SA[rk[i]-1]+k]) k++;H[rk[i]]=k;}
}
int main(){
    freopen("3518.in","r",stdin);freopen("3518.out","w",stdout);
    while (true){
        scanf("%s",s+1);n=strlen(s+1);if (s[1]=='#') break;Make(n);ans=0;
        for (int l=1;l<=(n>>1);l++)
            for (int i=1,j,MIN,MAX;i<=n;i=j){
                for (j=i+1;j<=n && H[j]>=l;j++);
                MIN=1e9;MAX=0;for (int k=i;k<j;k++) MIN=min(MIN,SA[k]),MAX=max(MAX,SA[k]);
                if (MAX-MIN>=l) ans++;
            }
        printf("%d\n",ans);
    }
    return 0;
}