`

最长重复子串和最长不重复子串求解

阅读更多

 

最长重复子串和最长不重复子串求解

本文内容框架:

§1 最长重复子串

基本方法、KMP算法求解、后缀数组求解

§2 最长不重复子串

基本方法、动态规划、动态规划+Hash

§3 小结

 

§1最长重复子串

 

1.1问题描述

 

首先这是一个单字符串问题。子字符串R 在字符串L 中至少出现两次,则称R 是L 的重复子串。重复子串又分为可重叠重复子串和不可重叠重复子串。

 

1.2基本方法

 

枚举子串,让子串和子串进行比较。直接看代码:

/* 最长重复子串 Longest Repeat Substring */
 
int maxlen;    /* 记录最长重复子串长度 */
int maxindex;  /* 记录最长重复子串的起始位置 */
void outputLRS(char * arr);  /* 输出LRS */
 
/* 最长重复子串 基本算法 */
int comlen(char * p, char * q)
{
    int len = 0;
    while(*p && *q && *p++ == *q++)
    {
        ++len;
    }
    return len;
}
 
void LRS_base(char * arr, int size)
{
    for(int i = 0; i < size; ++i)
    {
        for(int j = i+1; j < size; ++j)
        {
            int len = comlen(&arr[i],&arr[j]);
            if(len > maxlen)
            {
                maxlen = len;
                maxindex = i;
            }
        }
    }
    outputLRS(arr);
}

 ╝①

优化思路

一般的优化方法就是在充分利用已有的结果,最长重复子串的长度增加一定是建立在之前已经找到的重复子串之上的,充分利用已找到的重复子串的位置和长度是优化的一个重点,此外还有就是未不是重复子串的,以后就不会被包含在重复子串内,如"ab"只有一个,则重复子串就不能包含"ab"(允许重叠的重复子串例外)。

 

1.2KMP算法求解

 

对KMP算法还不是很了解的,可以查看我的另一篇博文(不懂猛点),在KMP算法的关键就是求解next数组,针对next[j]=k,可以得到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]。看到P[0,1,...,k-1]=P[j-k,j-k+1,...,j-1]应该会眼前一亮,大脑顿时清醒些,这不就是重复子串吗!由此求解最长重复子串就转化为求解KMP算法next数组中的最大值(即max{next[j]=k}。

现在就是求解next数组的问题了,还是直接查看代码:

 

int getNext(char *str,int *next)
{
	int len=strlen(str);
	int index=0;
	int k=-1;
	next[0]=k;
	int max=0;

	//kmp算法求next值,取得最大的字串
	while (index<len)
	{
		if (k==-1 || str[index]==str[k])
		{
			k++;
			index++;
			next[index]=k;
			if (k>max)//求得其中重复最大的字串的个数,也就是与最前面串的重复数
			{
				max=k;
			}
		}
		else
			k=next[k];
	}

	return max;
}

int main()
{
	char str[50];//输入字符串
	cin>>str;
	int max=0;//最大的字串
	int nextMax;//接受getNext函数中返回的最大值
	int index;
	int maxIndex;//保存最大的字串起始位置
	int len=strlen(str);
	//将一个字符串从开始一直减少到只剩一个字符,通过这个取得最小字串
	for (index=0;index<len-1;index++)
	{
		int *next=new int[len-index];//取得next在这没用
		nextMax=getNext(str+index,next);//每次从str+index开始
		if (nextMax>max)
		{
			max=nextMax;
			maxIndex=index;
		}
	}
	
	//输出最长字串
	cout<<"最长字串: ";
	for (index=0;index<max;index++)
	{
		cout<<str[index+maxIndex];
	}
	cout<<endl;
	
	return 0;
}

╝② 

 

1.3后缀数组求解

 

后缀数组在我的另外一篇博文有介绍,还没有概念的可以移步查看点击。后缀数组就是保留字符串所有位置到字符串末尾的子字符串,a[i]就是第i位置到末尾的子串。有了后缀数组,对后缀数组进行排序,然后进行求后缀数组相邻元素的最大前缀就是最大重复子串。

 

#include <iostream>
 using namespace std;
  
 const int MAXN = 1000;

 int mycmp(const void* p1, const void* p2)
 {
     return strcmp(*(char* const*)p1, *(char* const*)p2);
 }
 
 int getLen(char* p, char* q)
 {
     int ret = 0;
     while (*p && *p++ == *q++)
     {
         ++ret;
     }
     return ret;
 }
 
 char* foo(char result[], char s[])
 {
     int len = strlen(s);
     char** suffix = new char*[len];
     for (int i = 0; i < len; ++i)
     {
         suffix[i] = s + i;
     }
     qsort(suffix, len, sizeof (char*), mycmp);
     //for (int i = 0; i < len; ++i)
     //{
     //    cout << suffix[i] << endl;
     //}
     int maxlen = 0, maxi = 0, maxj = 0, temp = 0;
     for (int i = 0; i < len - 1; ++i)
     {
         temp = getLen(suffix[i], suffix[i + 1]);
         if (temp > maxlen)
         {
             maxlen = temp;
             maxi = i;
             maxj = i + 1;
         }
     }
     //cout << maxlen << endl;
     //cout << suffix[maxi] << endl;
     //cout << suffix[maxj] << endl;
     //printf("%.*s\n", maxlen, suffix[maxi]);
     for (int i = 0; i < maxlen; ++i)
     {
         result[i] = suffix[maxi][i];
     }
     result[maxlen] = '\0';
     return result;
 }
 
 int main()
 {
     char s[MAXN];
     char result[MAXN];
     while (cin >> s)
     {
         cout << foo(result, s) << endl;
     }
     return 0;
}

 

╝③

§2最长不重复子串 

2.1问题描述

 

从一个字符串中找到一个连续子串,该子串中任何两个字符不能相同,求子串的最大长度并输出一条最长不重复子串。

下面介绍四种方法逐步优化,时间复杂度从O(n²)到O(n)。

 

2.2基本算法(使用hash)

 

要求子串中的字符不能重复,判重问题首先想到的就是hash,寻找满足要求的子串,最直接的方法就是遍历每个字符起始的子串,辅助hash,寻求最长的不重复子串,由于要遍历每个子串故复杂度为O(n^2),n为字符串的长度,辅助的空间为常数hash[256]。

 

/* 最长不重复子串 设串不超过30
 * 我们记为 LNRS
 */
int maxlen;
int maxindex;
void output(char * arr);
 
/* LNRS 基本算法 hash */
char visit[256];
 
void LNRS_hash(char * arr, int size)
{
    int i, j;
    for(i = 0; i < size; ++i)
    {
        memset(visit,0,sizeof visit);
        visit[arr[i]] = 1;
        for(j = i+1; j < size; ++j)
        {
            if(visit[arr[j]] == 0)
            {
                visit[arr[j]] = 1;
            }else
            {
                if(j-i > maxlen)
                {
                    maxlen = j - i;
                    maxindex = i;
                }
                break;
            }
        }
        if((j == size) && (j-i > maxlen))
        {
            maxlen = j - i;
            maxindex = i;
        }
    }
    output(arr);
}

 

2.3动态规划求解

 

动态规划思想就是用于处理有重叠问题的求解,最大不重复子串一定是两个相同字符夹着的一段字符串加上这个字符,如abcac这里的最大不重复子串是a夹的一段。

当一个最长子串结束时(即遇到重复的字符),新的子串的长度是与第一个重复的字符的下标有关的,如果该下标在上一个最长子串起始位置之前,则dp[i] = dp[i-1] + 1,即上一个最长子串的起始位置也是当前最长子串的起始位置;如果该下标在上一个最长子串起始位置之后,则新的子串是从该下标之后开始的。简短几句话可能讲不是很明白,不过好在有程序可以帮助理解,惯例下面附上程序:

/* LNRS dp */
int dp[30];
 
void LNRS_dp(char * arr, int size)
{
    int i, j;
    int last_start = 0;     // 上一次最长子串的起始位置
    maxlen = maxindex = 0;
 
    dp[0] = 1;
    for(i = 1; i < size; ++i)
    {
        for(j = i-1; j >= last_start; --j) // 遍历到上一次最长子串起始位置
        {
            if(arr[j] == arr[i])
            {
                dp[i] = i - j;
                last_start = j+1; // 更新last_start
                break;
            }else if(j == last_start) // 无重复
            {
                dp[i] = dp[i-1] + 1;
            }
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

2.4动态规划+Hash求解

上面动态规划求解时间复杂度还是O(n²),主要是还是进行“回头”查找了重复元素位置,其实,上面并不是真正的动态规划方法,因为上面的求解过程没有记录有用的结果,所以可以通过记录之前出现的下标来改进算法,这样就不用每次都回去查找重复元素位置,这其实才是真正的动态规划方法,只是记录结果是用的Hash,这样的时间复杂度就是O(n)。

 

/* LNRS dp + hash 记录下标 */
void LNRS_dp_hash(char * arr, int size)
{
    memset(visit, -1, sizeof visit);
    memset(dp, 0, sizeof dp);
    maxlen = maxindex = 0;
    dp[0] = 1;
    visit[arr[0]] = 0;
    int last_start = 0;
 
    for(int i = 1; i < size; ++i)
    {
        if(visit[arr[i]] == -1)
        {
            dp[i] = dp[i-1] + 1;
            visit[arr[i]] = i; /* 记录字符下标 */
        }else
        {
            if(last_start <= visit[arr[i]])
            {
                dp[i] = i - visit[arr[i]];
                last_start = visit[arr[i]] + 1;
                visit[arr[i]] = i; /* 更新最近重复位置 */
            }else
            {
                dp[i] = dp[i-1] + 1;
            }
 
        }
        if(dp[i] > maxlen)
        {
            maxlen = dp[i];
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

 

 进一步优化

上面的程序因为辅助的空间多了,是不是还能优化,仔细看DP最优子问题解的更新方程:

dp[i] = dp[i-1] + 1;

dp[i-1]不就是更新dp[i]当前的最优解么?这与最大子数组和问题的优化几乎同出一辙,我们不需要O(n)的辅助空间去存储子问题的最优解,而只需O(1)的空间就可以了,至此,我们找到了时间复杂度O(N),辅助空间为O(1)(一个额外变量与256大小的散列表)的算法,代码如下:

注意:当前最长子串的构成是与上一次最长子串相关的,故要记录上一次最长子串的起始位置!

 

/* LNRS dp + hash 优化 */
void LNRS_dp_hash_impro(char * arr, int size)
{
    memset(visit, -1, sizeof visit);
    maxlen = maxindex = 0;
    visit[arr[0]] = 0;
    int curlen = 1;
    int last_start = 0;
 
    for(int i = 1; i < size; ++i)
    {
        if(visit[arr[i]] == -1)
        {
            ++curlen;
            visit[arr[i]] = i; /* 记录字符下标 */
        }else
        {
            if(last_start <= visit[arr[i]])
            {
                curlen = i - visit[arr[i]];
                last_start = visit[arr[i]] + 1;
                visit[arr[i]] = i; /* 更新最近重复位置 */
            }else
            {
                ++curlen;
            }
        }
        if(curlen > maxlen)
        {
            maxlen = curlen;
            maxindex = i + 1 - maxlen;
        }
    }
    output(arr);
}

 

 最后在给出测试用例

 

/* 输出LNRS */
void output(char * arr)
{
    if(maxlen == 0)
    {
        printf("NO LNRS\n");
    }
    printf("The len of LNRS is %d\n",maxlen);
 
    int i = maxindex;
    while(maxlen--)
    {
        printf("%c",arr[i++]);
    }
    printf("\n");
}
 
void main()
{
     char arr[] = "abcaacdeabacdefg";
 
     /* LNRS 基本算法 */
     LNRS_hash(arr,strlen(arr));
 
     /* LNRS dp */
     LNRS_dp(arr,strlen(arr));
 
     /* LNRS dp + hash 记录下标 */
     LNRS_dp_hash(arr,strlen(arr));
 
     /* LNRS dp + hash 优化方案 */
     LNRS_dp_hash_impro(arr,strlen(arr));
}

 ╝④

 

§3 小结

这篇文章把字符串最长重复子串和最长不重复子串的求解方法,能有了一定的认识和理解,基本可以掌握这些方法。如果你有任何建议或者批评和补充,请留言指出,不胜感激,更多参考请移步互联网。

 

 

参考:

勇幸|Thinking: http://www.ahathinking.com/archives/121.html

huang12315 http://blog.csdn.net/huang12315/article/details/6455090

unixfy http://www.cppblog.com/unixfy/archive/2011/05/23/146986.html

勇幸|Thinking: http://www.ahathinking.com/archives/123.html

 

 

 

 

 

1
0
分享到:
评论
2 楼 betabao 2016-06-26  
"最大不重复子串一定是两个相同字符夹着的一段字符串加上这个字符,如abcac这里的最大不重复子串是a夹的一段。" 这个判断是错误的,比如41234563,最大子串是123456,但两头分别是4和3.
1 楼 budingbuku110 2015-05-04  
在动态规划+hash求解的方法中,你的解法对于这种情况处理是不正确的,即,字符串是"qwnfenpglqdq"。应该在26行后面加一个char_map[s[i]] = i;

相关推荐

    python实现求两个字符串的最长公共子串方法

    在Python编程语言中,求解两个字符串的最长公共子串是一项常见的字符串处理任务。这个问题的解决方案通常基于动态规划思想,即将问题分解为更小的子问题,并存储子问题的解以便于后续使用,从而避免重复计算。下面...

    Manacher's ALGORITHM_ O(n)时间求字符串的最长回文子串 - Blog of Felix021 - Tec

    Manacher's 算法是一种高效解决字符串中最长回文子串问题的算法,它能在O(n)的时间复杂度内完成,其中n是字符串的长度...在LeetCode等在线编程平台上,该算法常用于解决字符串处理问题,特别是求解最长回文子串的问题。

    python实现对求解最长回文子串的动态规划算法

    动态规划的基本思想是将一个复杂的问题分解成若干个更小的子问题,然后通过存储和重用子问题的解来避免重复计算,从而提高效率。 对于最长回文子串的动态规划算法,我们可以定义一个二维数组`matrix`,其中`matrix...

    python-leetcode面试题解之无重复字符的最长子串.zip

    这个压缩包文件“python-leetcode面试题解之无重复字符的最长子串.zip”显然是一个关于解决LeetCode上特定问题的资源集合,问题的核心是寻找字符串中的最长无重复字符子串。 题目描述: 给定一个字符串`s`,找到...

    寻找字符串中最长的回文子串的长度

    Manacher's Algorithm的创新之处在于利用了回文串的对称性质来减少重复计算,通过维护一个回文半径中心P和回文右边界R,动态更新回文串的信息。当查找新位置i时,如果i在已知回文串的范围内,我们可以利用已知信息...

    利用C++实现最长公共子序列与最长公共子串

    最长公共子串的求解同样基于动态规划,但因为子串要求连续性,数组`c[i][j]`的含义有所不同,它记录的是以`str1[i-1]`和`str2[j-1]`结尾的最长公共子串的长度。状态转移方程变为: 最长公共子串的长度是所有`c[i][j...

    从“公共子串”的角度来分析求解“最长公共子序列”(LCS)

    而LCS则不同,它不要求连续性,所以 "AE" 也是 "ABCDEF" 和 "ABEFGH" 的一个最长公共子序列,尽管它不是公共子串。 接下来,我们将从算法的角度探讨如何求解LCS。一种常见的方法是使用动态规划,这在计算机科学中是...

    数组字符串那些经典算法 面试用

    寻找字符串中最长的不包含重复字符的子串,例如,字符串"abcabcbb"的最长不重复子串是"abc"。 **最长回文子串** 最长回文子串是指字符串中最长的回文序列,即正读反读都一样的子串。例如,"babad"的最长回文子串有...

    求回文子串_O(n)_manacher算法

    综上所述,Manacher算法作为一种专门针对回文子串求解的高效算法,通过巧妙的预处理和动态规划策略,将原本O(N^2)的复杂度降低至O(n),极大地提升了算法的性能。对于处理大规模数据集或需要快速响应的应用场景来说,...

    动态规划入门第4、5课

    本篇将深入探讨动态规划的两个实例:求解最长公共子串问题和取数游戏。 首先,我们来看第一个问题——求解两个小写字母组成的字符串的最长公共子串的长度。这个问题的核心在于定义状态和构建转移方程。我们可以用一...

    算法训练营【5】Manacher算法及其扩展(csdn)————程序.pdf

    Manacher算法是一种用于求解字符串中最长...总结来说,Manacher算法通过利用回文串的对称性,避免了重复计算,从而实现了线性时间复杂度的求解最长回文子串问题。这对于处理大规模数据非常有效,极大地提高了算法效率。

    后缀自动机的应用

    针对求解两个字符串的最长公共子串问题,如Spoj的LCS题目,我们可以采用以下策略: 1. **构造母串的后缀自动机**:首先,以其中一个字符串(母串A)为基础,构建后缀自动机。 2. **逐位扫描匹配串**:随后,逐字符...

    summary.docx

    本文将深入探讨四个与算法相关的知识点:单词矩阵中无重复字符的最长子串、处理不确定长度数组的输入、数独字符串求解以及识别三种括号的区别,以及最长公共子串问题。 首先,让我们讨论“单词矩阵无重复字符的最长...

    几道经典DP问题的解法

    =yj`且`i`和`j`均不为0,则`C[i,j]=max(C[i-1][j],C[i][j-1])`,表示当前字符不匹配,取两者之前的最大值作为当前的最长公共子串长度。 通过上述状态转移方程,最终可以在`C`矩阵中找到最长公共子串的长度及具体...

    A Collection of Dynamic Programming Interview Questions Solved in C++

    最长公共子序列问题与最长公共子串类似,不同的是,子序列不要求连续,而子串要求连续。动态规划同样适用于这个问题的解决。 17. 最长递增子序列(LIS) 最长递增子序列问题是在一个数组中找到最长的严格递增的子...

    手稿_V1.03

    5. **动态规划思想**:虽然这个问题不是标准的动态规划问题,但它具有动态规划的性质,即通过维护当前窗口的状态(长度和是否存在重复字符)来逐步求解全局最优解。 6. **优化策略**:在更新最大子串长度`ret_val`...

    最长公共子序列的动态规划算法

    我们需要找到这两个字符串的最长公共子序列,即在不改变顺序的情况下,X和Y共有的最长子串。在本例中,最长公共子序列是BCBA。 动态规划解决方案通常使用一个二维数组L[i, j],其中L[i, j]表示字符串X的前i个字符和...

    后缀数组——处理字符串的有力工具1

    4. **回文子串**:找到字符串中最长的回文子串,后缀数组结合Manacher's Algorithm等方法可以高效求解。 5. **连续重复子串**:寻找连续重复的子串及其出现次数,后缀数组同样适用。 6. **两个或多个字符串的相关...

Global site tag (gtag.js) - Google Analytics