记录编号	155816	评测结果	AAAAAAAAAA
题目名称	[SPOJ 705] 不同的子串	最终得分	100
用户昵称	HouJikan	是否通过	通过
代码语言	C++	运行时间	0.132 s
提交时间	2015-03-30 21:22:00	内存使用	1.31 MiB

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <list>
#include <vector>
#include <ctime>
#include <functional>
#define pritnf printf
#define scafn scanf
#define sacnf scanf
#define For(i,j,k) for(int i=(j);i<=(k);(i)++)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef unsigned int Uint;
const int INF=0x3fffffff;
const double eps=1e-10;
///==============struct declaration==============

///==============var declaration=================
const int MAXN=50010;
int n,k;
int sa[MAXN],rank[MAXN],h[MAXN],trank[MAXN],height[MAXN];
char str[MAXN];
///==============function declaration============
bool cmp(int a,int b){return rank[a]==rank[b]?rank[a+(1<<k)]<rank[b+(1<<k)]:rank[a]<rank[b];}
bool cmp1(int a,int b){return str[a]<str[b];}
///==============main code=======================
int main()
{
	//#define FILE__
	//#ifdef FILE__
   freopen("subst1.in","r",stdin);
   freopen("subst1.out","w",stdout);
	//#endif 
	scanf("%s",str+1);
	n=strlen(str+1);str[n+1]='$';n++;
	for(int i=0;i<=n;i++)
		sa[i]=i;
	sort(sa+1,sa+1+n,cmp1);
	rank[sa[1]]=1;
	for(int i=2;i<=n;i++)
		if (str[sa[i]]!=str[sa[i-1]])
			rank[sa[i]]=rank[sa[i-1]]+1;
		else
			rank[sa[i]]=rank[sa[i-1]];
	for(k=0;(1<<k)<=n;k++){
		sort(sa+1,sa+1+n,cmp);
		trank[sa[1]]=1;
		for(int i=2;i<=n;i++){
			if (rank[sa[i]]!=rank[sa[i-1]]||rank[sa[i]+(1<<k)]!=rank[sa[i-1]+(1<<k)])
				trank[sa[i]]=trank[sa[i-1]]+1;
			else
				trank[sa[i]]=trank[sa[i-1]];
		}
		for(int i=1;i<=n;i++)
			rank[i]=trank[i];
		if (rank[sa[n]]==n) break;
	}
	for(int i=1;i<=n;i++)
		rank[sa[i]]=i;
	///height[i]表示sa[rank[i]]和sa[rank[i-1]]的最长前缀
	height[rank[1]]=0;
	for(int i=1;i<=n;i++){
		height[rank[i]]=max(height[rank[i-1]]-1,0);
		int p=i,q=sa[rank[i]-1];
		while (str[p+height[rank[i]]]==str[q+height[rank[i]]])
			height[rank[i]]++;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		ans+=n-sa[i]-height[i];
  	printf("%lld\n",ans);
   return 0;
}
///================fuction code====================