题目:
给定一个字符串,求出其最长的重复子串(最长重复子串可以重叠)。
如字符串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;
}
分享到:
相关推荐
输入一行字符串,找出其中出现的相同且长度最长的字符串,输入它及其首字符的位置。例如“yyabcdabjcabceg”,输出结果应该为abc和3.
可以查询出一个字符串中重复出现且最长的子字符串
通过C++方法实现串中最大重复子串 初始设子串起始位置index=0,最长重复子串...再从s_(i+length1)之后找重复子串,然后对于s_(i+1)之后的字符采用相同的方法,最后的index与length即记录下最长重复子串的下表与长度。
打印出一个字符串中的最长的一个重复子串,并打印出重复的位置。
在字符串中查找最长重复子串的探讨 写一个函数,找出一个字符串中最长的重复子串。“t1t1”结果就是t1."cabcabca"结果就是cab或者abc或者bca。
在字符串中找到最长的不包含重复字符的子串,返回其长度
找出一个字符串中出现次数最多的子字符串,并返回重复次数。使用java编写
剑指offer.48
腾讯2011年10月15日校招笔试算法编程题
这个代码可以添加一个新的字符串到已有的字符串数组中,并确保不会重复添加相同的字符串。具体来说,它首先创建了一个包含3个字符串的字符串数组`strArray`,然后定义了一个新的字符串`newStr`。接着,使用`ismember...
如果要用一个和字符串a一样长的数组counter来计录a中各起点对应与b最大重合子字符串,这个数组也要和a一样长,空间上也不合适,除非情形很特殊,a短b长,不然不如直接malloc()一个堆空间来储存当前最长“子字符串”...
从键盘输入一串由数字组成的字符串,例如“234567910”,设计一个高效算法,输出字符串中的升序序列,该升序序列中的数字要么是差值为1的等差序列,要么只允许有一对相邻的数字差值为2,此时将该漏掉的数字找到并...
给定字符串,查找其中重复的子字符串积重复的次数[参考].pdf
最长不含重复字符的子字符串.md
最大重复子字符串给你一个字符串 sequence ,如果字符串 word 连续重复 k 次形成的字符串是 sequence 的一个子字符串,那么单词 word
找出字符串中最长的没有重复字符的子串,算法精巧,代码简洁
48. 最长不含重复字符的子字符串题目描述输入一个字符串(只包含 a\~z 的字符),求其最长不含重复字符的子字符串的长度。解题思路int preI = pre
剑指Offer(Python多种思路实现):最长不含重复字符的子字符串 面试48题: 题目:最长不含重复字符的子字符串 题:请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长字符串的长度。假设字符串中只包含...
本文实例讲述了Python查找最长不包含重复字符的子字符串算法。分享给大家供大家参考,具体如下: 题目描述 请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。例如在“arabcacfr”中...