题目：Boring counting
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3518
题意：给一个字符串，问有多少子串出现过两次以上，重叠不能算两次，比如ababa，aba只出现一次。
思路：
网上搜的题解估计大部分都是后缀数组，但字典树+优化是可以解决该问题的。
字典树解决这题难点就是内存，先不考虑内存，那么可以遍历起始点，然后添加入字典树，比如现在abab要添加进字典树，如果原本已经存在abab，并且两个不重叠，那么ans++，同时将abab标记掉，如果不存在，记录此时的下标以便等会判断是否重叠。（很简单的思路。）
现在解决内存，可以计算，如果要通过内存限制，字典树节点只能27万左右。但如果只设置这么大，最后会超出，会RE（G++好像会显示TLE），可以想象，字典树上很多节点的next[26]都是-1，浪费空间，因此可以把next[26]换成vector，动态申请，查找时多花一点时间遍历，但内存大大减小。
---------------------------------------------------------------------------------
下面是后缀数组解决该问题的方法：
首先要明白后缀数组里几个数组的用法，这里不详述了。
首先，我们可以遍历满足要求的字串的长度len，从1 到ls/2，然后遍历一遍height数组，height[i]表示排名第i 的后缀和排名第i-1 的后缀的最长公共前缀长度，那么如果height[i]>=len，这就有可能是答案了，只要不重叠就可以了，重叠可以用sa数组判断，可以找出最左边的下标记为l，最右边的下标记为r，只要l+len<=r就可以了，注意，height<len以后就是另外的字符串了。
AC代码：
#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
using namespace std;
struct Node
{
int val;
map<char,int> next;
}v[];
int vNum;
int ans;
void add(char *s,int start)
{
int p = ;
for(int i=start;s[i];i++)
{
int t = v[p].next[s[i]];
if(t!=) p = t;
else
{
v[vNum].val=-;
v[vNum].next.clear();
v[p].next[s[i]]=vNum++;
p=vNum-;
}
if(v[p].val!=-)
{
if(v[p].val!=- && v[p].val<start)
{
ans++;
v[p].val=-;
}
}
else v[p].val = i;
}
}
char s[];
int main()
{
while(~scanf("%s",s))
{
if(s[]=='#') break;
v[].val=-;
for(int i=;i<;i++) v[].next.clear();
vNum=;
ans=;
for(int i=;s[i];i++)
{
add(s,i);
}
printf("%d\n",ans);
}
return ;
}
字典树
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<set>
#include<map>
#include<list>
#include<stack>
#include<queue>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
#define lson rt<<1
#define rson rt<<1|1
#define N 1010
#define M 100010
#define Mod 1000000007
#define LL long long
#define INF 0x7fffffff
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define For(i,f_start,f_end) for(int i=f_start;i<f_end;i++)
#define REP(i,f_end,f_start) for(int i=f_end;i>=f_start;i--)
#define Rep(i,f_end,f_start) for(int i=f_end;i>f_start;i--)
#define MT(x,i) memset(x,i,sizeof(x))
#define gcd(x,y) __gcd(x,y)
const double PI = acos(-); char s1[];
int ws[N],wv[N];
int sa[N],r[N],wx[N],wy[N];
int height[N];
bool cmp(int *r,int a,int b,int l)
{
return r[a]==r[b]&&r[a+l]==r[b+l];
}
void da(int *r,int n,int m)
{
int *x=wx,*y=wy;
for(int i=;i<m;i++) ws[i]=;
for(int i=;i<n;i++) ws[x[i]=r[i]]++;
for(int i=;i<m;i++) ws[i]+=ws[i-];
for(int i=n-;i>=;i--) sa[--ws[x[i]]]=i;
int i,j,p,*t;
for(j=,p=;p<n;j*=,m=p)
{
for(p=,i=n-j;i<n;i++) y[p++]=i;
for(i=;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
for(i=;i<n;i++) wv[i]=x[y[i]];
for(i=;i<m;i++) ws[i]=;
for(i=;i<n;i++) ws[wv[i]]++;
for(i=;i<m;i++) ws[i]+=ws[i-];
for(i=n-;i>=;i--) sa[--ws[wv[i]]]=y[i];
for(t=x,x=y,y=t,p=,x[sa[]]=,i=;i<n;i++)
x[sa[i]]=cmp(y,sa[i],sa[i-],j)?p-:p++;
}
for(int i=;i<n;i++)
{
r[sa[i]]=i;
}
}
void calHeight(int n)
{
int h=;
for(int i=;i<n;i++)
{
if(r[i]==) h=;
else
{
int k=sa[r[i]-];
if(--h<) h=;
while(s1[k+h]==s1[i+h]) h++;
}
height[r[i]]=h;
}
} int main()
{
while(~scanf("%s",s1))
{
if(s1[]=='#') break;
int ls = strlen(s1);
for(int i=;i<ls;i++)
{
r[i]=s1[i]-'a'+;
}
r[ls++]=;
da(r,ls,);
calHeight(ls);
int ans = ;
for(int i=;i<=(ls-)/;i++)
{
int flag = ;
int l=INF,r=-;
for(int j=;j<ls;j++)
{
if(height[j]>=i)
{
l = min(sa[j],min(sa[j-],l));
r = max(sa[j],max(sa[j-],r));
if(flag==&&l+i<=r)
{
ans++;
flag=;
}
}
else
{
flag=;
l=INF;
r=-;
}
}
}
printf("%d\n",ans);
}
return ;
}
后缀数组