后缀数组求最长重复子串

问题描述
给定一个字符串,求出其最长重复子串
例如:abcdabcd
最长重复子串是 abcd,最长重复子串可以重叠

例如:abcdabcda,这时最长重复子串是 abcda,中间的 a 是被重叠的。


改进的方法是利用后缀数组
后缀数组是一种数据结构,对一个字符串生成相应的后缀数组后,然后再排序,排完序依次检测相邻的两个字符串的开头公共部分。
这样的时间复杂度为:生成后缀数组 O(N),排序 O(NlogN*N) 最后面的 N 是因为字符串比较也是 O(N)
依次检测相邻的两个字符串 O(N * N),总的时间复杂度是 O(N^2*logN),优于第一种方法的 O(N^3)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxLen = 5000;

char c[maxLen];
char *a[maxLen];

bool cmp(char *a, char *b){
	return strcmp(a, b) < 0 ? true : false;
}

int comLen(char *a, char *b){
	int cnt = 0;
	while (*a && (*a++ == *b++)) cnt++;
	return cnt;
}

int main(){

	char ch;
	int n = 0;
	while ((ch = getchar()) != '\n'){
		a[n] = &c[n];
		c[n++] = ch;
	}

	c[n] = '\0';//

	sort(a, a + n, cmp);

	int maxLen = INT_MIN;
	char maxi;
	for (int i = 0; i < n-1; i++){
		int tmp = comLen(a[i], a[i + 1]);
		if (tmp>maxLen){
			maxLen = tmp;
			maxi = i;
		}
	}

	printf("%.*s", maxLen, a[maxi]);

	return 0;
}
相关文章
相关标签/搜索