求字符串最长的重复子串

题目：
给定一个字符串，求出其最长的重复子串（最长重复子串可以重叠）。
如字符串abcdabcabcd，其最长的重复子串为abcd；
如字符串abcdabcda，其最长的重复子串为abcda。

算法思想：
对字符串生成相应的后缀数组，再对其排序，排序后依次检测相邻两个字符串的公共前缀，时间复杂度为O(N^2*logN)。

程序如下：

#include<iostream>
using namespace std;

#define MAX 256

/* 定义全局变量 */
char str[MAX];
char *suffix_array[MAX];// 对于长度为n的字符串，其后缀数组的长度亦为n（存放n个后缀字符串）

/* 初始化字符串与其后缀数组 */
void suffix(char *str, char **suffix_array)
{
	int i = 0;
	char ch;
	while((ch = getchar()) != '\n')
	{
		str[i] = ch;
		suffix_array[i] = &str[i];
		i++;
	}
	str[i] = '\0';
}

/* 冒泡排序 */
void bubbleSort(char **suffix_array, int n)
{
...
}

/* 快速排序 */
void quickSort(char **suffix_array, int left, int right)
{
...
}

/* 返回两个字符串公共前缀的最大长度 */
int compLen(char *str1, char *str2)
{
	int len = 0;
	while (*str1 && *str1 == *str2)
	{
		len++;
		str1++;
		str2++;
	}
	return len;
}

/* 由排序后的后缀数组，求得最长的重复子串的长度 */
char* assignStrWithMaxLen(char *dest, char **sorted_suffix_array, int n)
{
	int max = 0;
	int beginIndex = -1;
	for (int i = 0; i < n - 1; i++)
	{
		int tmp = compLen(sorted_suffix_array[i], sorted_suffix_array[i + 1]);
		if (tmp > max)
		{
			max = tmp;
			beginIndex = i;
		}
	}

	strncpy(dest, sorted_suffix_array[beginIndex], max);

	return dest;
}

int main()
{
	suffix(str, suffix_array);
	int n = strlen(str);// 字符串字符的个数，也是后缀字符串的个数

	/* 对后缀数组进行排序 */
	//bubbleSort(suffix_array, n);
	quickSort(suffix_array, 0, n - 1);

	char dest[MAX] = {'\0'};
	assignStrWithMaxLen(dest, suffix_array, n);
	cout << dest << endl;
	
	return 0;
}

复习排序算法：

/* 冒泡排序 */
void bubbleSort(char **suffix_array, int n)
{
	for (int i = 0; i < n; i++)// i表示已在最终位置的元素的个数
	{
		int flag = 1;
		for (int j = 0; j + 1 < n - i; j++)// 后i个元素已有序，只需前(n-i)个元素比较
		{
			if (strcmp(suffix_array[j], suffix_array[j + 1]) > 0)
			{
				swap(suffix_array[j], suffix_array[j + 1]);
				flag = 0;
			}
		}
		if (flag == 1)
		{
			break;
		}
	}
}

/* 快速排序 */
void quickSort(char **suffix_array, int left, int right)
{
	if (left < right)
	{
		char *pivot = suffix_array[left];
		int i = left, j = right;
		while (i < j)
		{
			while (i < j && strcmp(suffix_array[j], pivot) >= 0)
			{
				j--;
			}
			if (i < j)
			{
				swap(suffix_array[i++], suffix_array[j]);
			}

			while (i < j && strcmp(suffix_array[i], pivot) <= 0)
			{
				i++;
			}
			if (i < j)
			{
				swap(suffix_array[i], suffix_array[j--]);
			}
		}
		suffix_array[i] = pivot;// 此时i=j

		quickSort(suffix_array, left, i - 1);
		quickSort(suffix_array, i + 1, right);
	}
}

void swap(char *&ptr1, char *&ptr2)
{
	char *tmp = ptr1;
	ptr1 = ptr2;
	ptr2 = tmp;
}