通过后缀数组求字符串中最长重复字串

最新推荐文章于 2020-04-14 13:09:44 发布

codingkid

最新推荐文章于 2020-04-14 13:09:44 发布

阅读量676

点赞数

CC 4.0 BY-SA版权

分类专栏： coding note|代码笔记文章标签： include string

本文链接：https://blog.csdn.net/codingkid/article/details/6988736

coding note|代码笔记专栏收录该内容

12 篇文章

订阅专栏

本文介绍了一种通过快速排序算法实现后缀数组的方法，并详细展示了如何比较两个字符串的前缀长度来找到最长公共前缀的过程。代码示例使用 C++ 实现，包括自定义的字符串比较函数和打印函数。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

#include <iostream>
#include <cstring>
#include <stdlib.h>

using namespace std;
#define MAXLEN 100

int print(char **a,const int len)
{
	for(int i=0;i<len;i++)
		cout<<*(a+i)<<endl;
	return 0;
}

int comlen(char *a,char *b)
{
	int len = strlen(a)>strlen(b)?strlen(a):strlen(b);
	int max = 0;
	while((max<len)&&(a[max]==b[max]))
		max++;
	return max;
}

static int cmpstringp(const void *p1,const void *p2)
{
	cout<<"p1: "<<*(char * const *) p1<<" p2: "<<*(char * const *) p2<<endl;
	cout<<"strcmp:"<<strcmp(* (char * const *) p1, * (char * const *) p2)<<endl;
	return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int mysort(char **a,const int len)
{
	int maxlen =0;
	int prelen = maxlen;
	int maxi = -1;
	//quick sort and strcmp function
	qsort(&a[0],len,sizeof(a[0]),cmpstringp);

	print(a,len);
	//find maxlen
	for(int i=0;i<len;i++)
	{
		prelen = maxlen;
		maxlen = comlen(a[i],a[i+1])>maxlen?comlen(a[i],a[i+1]):maxlen;
		if(prelen!=maxlen)
			maxi = i;
	}
	if(maxi == -1)
	{
		cout<<"not found"<<endl;
		return 0;
	}
	cout<<"max length is : "<<maxlen<<" string is : "<<a[maxi]<<endl;
	return 0;
}

int main()
{
	char word[]="banana";
	int len = strlen(word);
	char *a[MAXLEN];
	int n=0;
	while(n<len)
	{
		a[n]=&word[n];
		n++;
	}
	print(a,len);
	cout<<"sort"<<endl;
	mysort(a,len);

	return 0;
}

分解为后缀数组，qsort排序，遍历一遍后缀数组两两相连的Str1,str2，是否str1是str2的前缀？若是，if>max刷新纪录。