<commit_before>---
layout: post
title: 后缀数组总结
tags: [about, Jekyll, theme, responsive]
comments: true
image:
  feature: 4.jpg
---

最近接触到了后缀数组，可以说是我至今为止遇到的最复杂的数据结构了，从查资料到把他搞懂花了两天的时间，现把它做一个小小的总结。后缀数组是一种非常强大的处理字符串问题的数据结构，目前有两种方法构造后缀数组，一种是倍增算法，时间复杂度为O(NlogN)。优点是实现简单，内存较少。另一种是DC3算法，时间复杂度为O(N),但是常数较大而且所占内存较大。实际上，由于倍增算法便于实现，时间复杂度也并不比DC3算法差多少，所以其使用的频率要高于DC3算法。现将倍增算法总结如下。


####倍增算法构造后缀数组

{% highlight c %}
const int maxn = 500;
int wa[maxn] ,wb[maxn], wv[maxn],ws[maxn],sa[maxn];
int cmp(int *r, int a, int b, int l){
	return r[a] == r[b] && r[a+l] == r[b+l];
}
/*****************************************************
功能：倍增法求排序后的后缀数组
参数：r   指向原字符串数组
	  sa  结果后缀数组
	  n   字符串的长度+1 添加最后一个字符 区别比较
      m   字符串包含不同字符的个数，一般128可以满足
*****************************************************/
void da(int *r,int *sa,int n,int m)//倍增法实现后缀数组
{ 
	int i,j,p,*x=wa,*y=wb;
	// 基数排序  ，确定字符串长度为1时的顺序
	for(i = 0;i < m;i++) ws[i] = 0;         //先对ws清零
	for(i = 0;i < n;i++) ws[x[i] = r[i]]++;//将原串从左到右入桶
	for(i = 1;i < m;i++) ws[i] += ws[i-1];  //求部分和序列，以便出桶时确定下标
	for(i=n-1;i >=0;i--) sa[--ws[x[i]]] = i;//从右到左出桶
	//多次基数排序，先按照第二关键字排序，在按照第一关键字排序
	for(j = 1,p = 1;p<n; j *= 2,m = p){
		//对第二关键字排序
		for(p = 0,i=n-j;i<n;i++) y[p++]=i; //最开始求长度2的字符串的第二关键字，末尾不足j+1的后缀，排序在最前面，因为默认原串后面的字符最小
		for(i = 0;i<n;i++)	if(sa[i] >= j) y[p++] = sa[i] - j;//优化：按照上次排序后的结果，sa
		for(i = 0;i<n;i++)  wv[i] = x[y[i]];//排序后的字符存在wv中
		//对第一关键字排序
		for(i = 0;i < m;i++) ws[i] = 0;
		for(i = 0;i < n;i++) ws[wv[i]]++; //是上面排序结果，要对它进行基数排序
		for(i = 1;i < m;i++) ws[i] += ws[i-1];
		for(i=n-1;i >=0;i--) sa[--ws[wv[i]]] = y[i];//y[i]是按第二关键字排名的‘sa’数组
		//判断有没有相同的长度为j+1的字符串，若没有，则已得到后缀数组
		swap(x,y); //交换x,y指向，因为下一此循环，y数组的计算要利用x数组，而现在的y数组是下一次的x数组应有的内容
		for(p=1,x[sa[0]] = 0,i=1;i < n;i++) //x[sa[0]] = 0
			x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1:p++;//比较相邻的后缀数组有没有相同的字符,没有的话p=n，退出循环
	}
	return;
}
{% endhighlight %}

####计算height数组

{% highlight c %}
/*****************************************************
功能：计算height数组
参数：r   指向原字符串数组
	  sa  后缀数组
	  n   字符串的长度
*****************************************************/
int Rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n){
	int i, j, k = 0;
	for(i = 1;i<=n;i++)
		Rank[sa[i]] =i; //根据sa求rank
	for(i = 0;i < n;height[Rank[i++]] = k) //h[i] = height[rank[i]]
		for(k?k--:0,j = sa[Rank[i]-1];r[i+k] == r[j+k];k++);//h[i] >=h[i-1]-1;可以优化此计算
}

{% endhighlight %}

---

####应用：求最长回文子串

{% highlight c %}
/*****************************************************
功能：求字符串的最长回文子串。方法是将原字符串逆序放在
	  后面，中间用一个较小字符隔开比如'$'
	  str中保存
*****************************************************/
char str[maxn];
void longestPalindrome(void){
	int n = strlen(str);
	int i,j,r[maxn];
	str[n] = '$';
	for(i = n-1,j=n+1;i >= 0;i--,j++)
		str[j] = str[i];
	for(i = 0;i<2*n+1;i++)
		r[i] = str[i];
	r[2*n+1] = 0;
	da(r,sa,2*n+2,128);
	calheight(r,sa,2*n+1);
	int max = 0,start = 0;
	for(i = 1;i < 2*n+2;i++)
		if(height[i] > max && (sa[i-1] < n) ^ (sa[i] < n)){
			max = height[i];
			start = sa[i];
		}
	for(i = start;i<start+max;i++) printf("%c",str[i]);
}

{% endhighlight %}

####测试

{% highlight c %}

int main()
{ 
	scanf("%s",str);       //输入 abaaabcaa
	longestPalindrome();   //输出 baaab
	return 0;
}

{% endhighlight %}

关于后缀数组的更多内容，请参考


<div markdown="0"><a href="http://files.cnblogs.com/newpanderking/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%A4%84%E7%90%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%9C%89%E5%8A%9B%E5%B7%A5%E5%85%B7.pdf" class="btn btn-danger">后缀数组</a></div>


<section id="table-of-contents" class="toc">
  <header>
    <h3>Overview</h3>
  </header>
<div id="drawer" markdown="1">
*  Auto generated table of contents
{:toc}
</div>
</section><!-- /#table-of-contents --><commit_msg>add new post<commit_after>---
layout: post
title: 后缀数组总结
tags: [about, Jekyll, theme, responsive]
comments: true
image:
  feature: 4.jpg
---

最近接触到了后缀数组，可以说是我至今为止遇到的最复杂的数据结构了，从查资料到把他搞懂花了两天的时间，现把它做一个小小的总结。后缀数组是一种非常强大的处理字符串问题的数据结构，目前有两种方法构造后缀数组，一种是倍增算法，时间复杂度为O(NlogN)。优点是实现简单，内存较少。另一种是DC3算法，时间复杂度为O(N),但是常数较大而且所占内存较大。实际上，由于倍增算法便于实现，时间复杂度也并不比DC3算法差多少，所以其使用的频率要高于DC3算法。现将倍增算法总结如下。


####倍增算法构造后缀数组

{% highlight c %}
const int maxn = 500;
int wa[maxn] ,wb[maxn], wv[maxn],ws[maxn],sa[maxn];
int cmp(int *r, int a, int b, int l){
	return r[a] == r[b] && r[a+l] == r[b+l];
}
/*****************************************************
功能：倍增法求排序后的后缀数组
参数：r   指向原字符串数组
	sa  结果后缀数组
	n   字符串的长度+1 添加最后一个字符 区别比较
	m   字符串包含不同字符的个数，一般128可以满足
*****************************************************/
void da(int *r,int *sa,int n,int m)//倍增法实现后缀数组
{ 
	int i,j,p,*x=wa,*y=wb;
	// 基数排序  ，确定字符串长度为1时的顺序
	for(i = 0;i < m;i++) ws[i] = 0;         //先对ws清零
	for(i = 0;i < n;i++) ws[x[i] = r[i]]++;//将原串从左到右入桶
	for(i = 1;i < m;i++) ws[i] += ws[i-1];  //求部分和序列，以便出桶时确定下标
	for(i=n-1;i >=0;i--) sa[--ws[x[i]]] = i;//从右到左出桶
	//多次基数排序，先按照第二关键字排序，在按照第一关键字排序
	for(j = 1,p = 1;p<n; j *= 2,m = p){
		//对第二关键字排序
		for(p = 0,i=n-j;i<n;i++) y[p++]=i; //最开始求长度2的字符串的第二关键字，末尾不足j+1的后缀，排序在最前面，因为默认原串后面的字符最小
		for(i = 0;i<n;i++)	if(sa[i] >= j) y[p++] = sa[i] - j;//优化：按照上次排序后的结果，sa
		for(i = 0;i<n;i++)  wv[i] = x[y[i]];//排序后的字符存在wv中
		//对第一关键字排序
		for(i = 0;i < m;i++) ws[i] = 0;
		for(i = 0;i < n;i++) ws[wv[i]]++; //是上面排序结果，要对它进行基数排序
		for(i = 1;i < m;i++) ws[i] += ws[i-1];
		for(i=n-1;i >=0;i--) sa[--ws[wv[i]]] = y[i];//y[i]是按第二关键字排名的‘sa’数组
		//判断有没有相同的长度为j+1的字符串，若没有，则已得到后缀数组
		swap(x,y); //交换x,y指向，因为下一此循环，y数组的计算要利用x数组，而现在的y数组是下一次的x数组应有的内容
		for(p=1,x[sa[0]] = 0,i=1;i < n;i++) //x[sa[0]] = 0
			x[sa[i]] = cmp(y,sa[i-1],sa[i],j) ? p-1:p++;//比较相邻的后缀数组有没有相同的字符,没有的话p=n，退出循环
	}
	return;
}
{% endhighlight %}

####计算height数组

{% highlight c %}
/*****************************************************
功能：计算height数组
参数：r   指向原字符串数组
sa  后缀数组
n   字符串的长度
*****************************************************/
int Rank[maxn],height[maxn];
void calheight(int *r,int *sa,int n){
	int i, j, k = 0;
	for(i = 1;i<=n;i++)
		Rank[sa[i]] =i; //根据sa求rank
	for(i = 0;i < n;height[Rank[i++]] = k) //h[i] = height[rank[i]]
		for(k?k--:0,j = sa[Rank[i]-1];r[i+k] == r[j+k];k++);//h[i] >=h[i-1]-1;可以优化此计算
}

{% endhighlight %}

---

####应用：求最长回文子串

{% highlight c %}
/*****************************************************
功能：求字符串的最长回文子串。方法是将原字符串逆序放在
后面，中间用一个较小字符隔开比如'$'
str中保存
*****************************************************/
char str[maxn];
void longestPalindrome(void){
	int n = strlen(str);
	int i,j,r[maxn];
	str[n] = '$';
	for(i = n-1,j=n+1;i >= 0;i--,j++)
		str[j] = str[i];
	for(i = 0;i<2*n+1;i++)
		r[i] = str[i];
	r[2*n+1] = 0;
	da(r,sa,2*n+2,128);
	calheight(r,sa,2*n+1);
	int max = 0,start = 0;
	for(i = 1;i < 2*n+2;i++)
		if(height[i] > max && (sa[i-1] < n) ^ (sa[i] < n)){
			max = height[i];
			start = sa[i];
		}
	for(i = start;i<start+max;i++) printf("%c",str[i]);
}

{% endhighlight %}

####测试

{% highlight c %}

int main()
{ 
	scanf("%s",str);       //输入 abaaabcaa
	longestPalindrome();   //输出 baaab
	return 0;
}

{% endhighlight %}

####参考资料

关于后缀数组的更多内容，请参考


<div markdown="0"><a href="http://files.cnblogs.com/newpanderking/%E5%90%8E%E7%BC%80%E6%95%B0%E7%BB%84%E2%80%94%E2%80%94%E5%A4%84%E7%90%86%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%9C%89%E5%8A%9B%E5%B7%A5%E5%85%B7.pdf" class="btn btn-danger">后缀数组</a></div>


<section id="table-of-contents" class="toc">
  <header>
    <h3>Overview</h3>
  </header>
<div id="drawer" markdown="1">
*  Auto generated table of contents
{:toc}
</div>
</section><!-- /#table-of-contents -->
{'fraction_non_alphanumeric': 0.3203463203463203, 'fraction_numerical': 0.0367965367965368, 'mean_word_length': 4.858161648177496, 'pattern_counts': {'":': 0, '<': 65, '<?xml version=': 0, '>': 41, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '363832', 'n_tokens_mistral': 4682, 'n_tokens_neox': 4803, 'n_words': 533}