学步园

输入一个字符串 "abcderabcmnpqabcdmnp"，求出这个字符串的最长重复字串，

这个字符串的最长公共字串是abcd。

C语言代码如下：

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

void HouZhui(char *p);
int main()
{
  char a[100] = "abcderabcmnpqabcdmnp";
  HouZhui(a);
  return 0;
}

void HouZhui(char *p)
{
	void Qsort(char **p, int n);//对后缀数组排序
	int FindSame(char *, char *);//
	int n;
	int i;
	int max; //最长重复字串的长度
	int count;
	char *result;//结果的字符串
	char **q;
	char **first; 
	char **second;//遍历后缀数组
	if(p == NULL)
		return;
	n = strlen(p);
	q = (char **)malloc(sizeof(char *) * n);
	if(q == NULL)
		return;
	for(i = 0; i < n; ++i)
		q[i] = p+i;
	Qsort(q, n);

	for(i = 0; i < n; ++i)//观察排序结果
		printf("%s\n", q[i]);
	printf("\n");

	first = q;
	second = q+1;
	max = 0; 
	count = 0;
	result = *first;
	while(second <= q+n-1)
	{
		count = FindSame(*first, *second);
		if(count > max)
		{
			max = count;
			result = *first;
		}
		first++;
		second++;
	}
	while(max)
	{
		printf("%c", *result);
		result++;
		max--;
	}
	printf("\n");
	free(q);
}

int FindSame(char *a, char *b)//寻找两个字符串的公共前缀的长度
{
	int count = 0;
	while(*a != '\0' && *b != '\0' && *a == *b)
	{
		a++;
		b++;
		count++;
	}
	return count;
}

void Qsort(char **p, int n)//对生成的后缀数组排序
{
	int compare(char *a, char *b);
	void swap(char **a, char **b);
	int i, j;
	char *temp;
	if(n <= 1)
		return;
	j = -1;
	temp = p[n/2];
	swap(p+n/2, p+n-1);
	for(i = 0; i < n-1; ++i)//这里不要弄错了
	{
		if(compare(p[i], temp))//p[i] 小于temp
		{
			j++;
			if(j != i)
			{
				swap(p+i, p+j);
			}
		}
	}
	swap(p+n-1, p+j+1);
	Qsort(p, j+1);
	Qsort(p+j+2, n-j-2);
}

void swap(char **a, char **b)
{
	char *temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

int compare(char *a, char *b)//不存在a和b长度相同的情况
{
	while(*a != '\0' && *b != '\0' && *a == *b)
	{
		a++;
		b++;
	}
	if((*a == '\0') || *a < *b)
		return 1;
	else
		return 0;
}