/* 
	一个月前，我和上帝都知道这段代码的意思;
 	一个月后，就只有上帝知道了。  
*/

/******* Pre-treat: include *****/
#define Pre_treat_include

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/******* Pre-treat: define ******/
#define Pre_treat_define 1
#if Pre_treat_define

#define OpenFile 0
#define MAX_DATA 300000
#define MAX_LEN 300
#define MAX_ASK_DATA 100
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define Abs(x) (((x)>0)?(x):(-(x)))
#define GOP(x) ((x)>0?1:-1)

#endif
/********* Struct ***************/
#define Definition_Strict
struct String
{
	char str[MAX_DATA];
	int len;
};
struct Node
{
	int l,r,p;
	long long dat;
	int father;
	int num_a,num_b;
	int num_a_l,num_b_l;
	int num_a_r,num_b_r;
};
/********* Var ******************/
#define Definition_Var
struct String s;
int sa[MAX_DATA];
int rank[MAX_DATA];
int h[MAX_DATA];
int height[MAX_DATA];
int t1[MAX_DATA];
int t2[MAX_DATA];
int rank2[MAX_DATA];
int rank1[MAX_DATA];
int tt[MAX_DATA];
int tt2[MAX_DATA];
int ask[MAX_ASK_DATA][2];
int ask_n;
int LCP_ans[MAX_ASK_DATA];
//int t3[MAX_DATA];
//int t4[MAX_DATA];
struct Node descar[MAX_DATA];
int head_descar;
/********* declare **************/
#define Definition_declare

/********* Function *************/
#define Definition_Function
void Init_t()
{
	int i;
	for(i=0;i<MAX_DATA;i++)
	{
		t1[i]=0;
		t2[i]=0;
	}
}

void Get_Rank_f(int x)
{
	int i,j;
	if(x==1)	/* SA1基数排序 */
	{
		Init_t();
		for(i=1;i<=s.len+1;i++)	t1[s.str[i]]++;
		for(i=1;i<MAX_LEN;i++)	t2[i]=t2[i-1]+t1[i-1];
		for(i=1;i<=s.len+1;i++)	rank[i]=t2[s.str[i]];
	}
/*快排位置备份*/

	else
	{
		for(i=1;i<=s.len;i++)	/* 一，二关键字分离 */
		{
			rank1[i]=rank[i];
			if(i+x/2<=s.len)	rank2[i]=rank[i+x/2];
			else	rank2[i]=0;
		}
		Init_t();	/* 第一关键字 */
		t2[0]=1;
		for(i=1;i<=s.len;i++)	t1[rank2[i]]++;
		for(i=1;i<=s.len;i++)	t2[i]=t2[i-1]+t1[i-1];
		for(i=1;i<=s.len;i++)	tt[ t2[rank2[i]]++ ]=i;
		Init_t();	/* 第二关键字 */
		t2[0]=1;
		for(i=1;i<=s.len;i++)	t1[ rank1[tt[i]] ]++;
		for(i=1;i<MAX_DATA;i++)	t2[i] = t2[i-1] + t1[i-1];
		for(i=1;i<=s.len;i++)	tt2[ t2[rank1[tt[i]]]++ ] = tt[i];
		for(i=1;i<=s.len;i++)	/* 从tt到rank */
		{
			rank[tt2[i]]=i;
			if(rank1[tt2[i]]==rank1[tt2[i-1]]&&rank2[tt2[i]]==rank2[tt2[i-1]])
				rank[tt2[i]]=rank[tt2[i-1]];
		}
	 }
	if(x>s.len)	return;	/* 倍增 */
	Get_Rank_f(x*2);
}
void Get_Sa()
{
	int i;
	for(i=1;i<=s.len;i++)
		sa[rank[i]]=i;
	return;
}

void Get_Rank()
{
	Get_Rank_f(1);
}
void Get_H()
{
	int i,j;
	h[0]=0;
	for(i=1;i<=s.len;i++)	/* h[i]>=h[i-1]-1 */ 
	{
		if(h[i-1]<1)	
			j=0;
		else	
			j=h[i-1]-1;
		while(s.str[i+j]==s.str[sa[rank[i]-1]+j])	j++;
		h[i]=j;
	}
}

void Get_Height()
{
	int i;
	for(i=1;i<=s.len;i++)	
		height[rank[i]]=h[i];
}

int BuildTree()
{
	int i,j;
	int stack_LCP[MAX_DATA],top_LCP;
	top_LCP=0;
	stack_LCP[1]=0;
	for(i=1;i<MAX_DATA;i++)
	{
		descar[i].dat=0;
		descar[i].father=0;
		descar[i].l=0;
		descar[i].r=0;
		descar[i].p=0;
		descar[i].num_a=0;
		descar[i].num_b=0;
		descar[i].num_a_l=0;
		descar[i].num_b_l=0;
		descar[i].num_a_r=0;
		descar[i].num_b_r=0;		
	}
	for(i=3;i<=s.len;i++)
	{
		descar[i].dat=height[i];
		descar[i].father=0;
		descar[i].l=0;
		descar[i].r=0;
		descar[i].p=0;
		descar[i].num_a=0;
		descar[i].num_b=0;
		descar[i].num_a_l=0;
		descar[i].num_b_l=0;
		descar[i].num_a_r=0;
		descar[i].num_b_r=0;
		while(top_LCP>=0)
		{
			if(top_LCP==0)
			{
				descar[i].l=stack_LCP[1];
				descar[descar[i].l].p=i;
				break;
			}
			if(descar[stack_LCP[top_LCP]].dat<=descar[i].dat)
			{
				descar[i].p=stack_LCP[top_LCP];
				descar[i].l=descar[stack_LCP[top_LCP]].r;
				descar[descar[i].p].r=i;
				descar[descar[i].l].p=i;
				break;
			}
			top_LCP--;
		}
		top_LCP++;
		stack_LCP[top_LCP]=i;
	}
	head_descar=stack_LCP[1];
	return stack_LCP[1];
}

void SA_GetAll()
{
	int i;
	for(i=0;i<MAX_DATA;i++)
	{
		rank[i]=0;
		rank1[i]=0;
		rank2[i]=0;
		height[i]=0;
		h[i]=0;
		sa[i]=0;
	}
	Get_Rank();
	Get_Sa();
	Get_H();
	Get_Height();
}
/********* Main *****************/
char s1[MAX_DATA];
int k;
int a_len,b_len;
long long ans;

void dfs(int x)
{
	long long t=0;
	long long t1=0;
	long long t2=0;
	long long t3;
	if(descar[x].l!=0)
		dfs(descar[x].l);
	if(descar[x].r!=0)
		dfs(descar[x].r);
	if(descar[x].l!=0)
	{
		descar[x].num_a_l+=descar[descar[x].l].num_a;
		descar[x].num_b_l+=descar[descar[x].l].num_b;
	}
	if(descar[x].r!=0)
	{
		descar[x].num_a_r+=descar[descar[x].r].num_a;
		descar[x].num_b_r+=descar[descar[x].r].num_b;
	}
	if(sa[x-1]<=a_len && descar[x].l==0)	descar[x].num_a_l++;
	if(sa[x-1]>a_len && descar[x].l==0)		descar[x].num_b_l++;
	if(sa[x]<=a_len && descar[x].r==0)		descar[x].num_a_r++;
	if(sa[x]>a_len && descar[x].r==0)		descar[x].num_b_r++;
	descar[x].num_a=descar[x].num_a_l+descar[x].num_a_r;
	descar[x].num_b=descar[x].num_b_l+descar[x].num_b_r;
	if(descar[x].dat>=k)
	{
		t1 =descar[x].num_a_l;
		t1*=descar[x].num_b_r;
		t2 =descar[x].num_b_l;
		t2*=descar[x].num_a_r;
		t3 =descar[x].dat-k+1;
		ans+=(t1+t2)*t3;
	}
}

void InitS()
{
	scanf("%s",s1);
	a_len=strlen(s1);
	s.str[1]='\0';
	strcat(s.str+1,s1);
	s.len=a_len;
	s.str[s.len+1]='$';
	s.str[s.len+2]='\0';
	
	scanf("%s",s1);
	b_len=strlen(s1);
	strcat(s.str+1,s1);
	s.len=a_len+b_len+1;
	s.str[s.len+1]='!';
	s.str[s.len+2]='\0';	
}
int main(int argc, char *argv[])
{
	int i,j;
	while(1)
	{
		scanf("%d",&k);
		if(k==0)
			return 0;
		InitS();
		SA_GetAll();
		BuildTree();
		ans=0;
		dfs(head_descar);
		printf("%I64d\n",ans);
	}
	return 0;
}
/********* END ******************/

• Re:求解释 为什么会RE啊~~~~ 用后缀数组+笛卡尔树 (37) wzk_DTerH 2012-01-29 17:32:37