首页 > 算法 数据结构 > 最长不重复子串

最长不重复子串

2012年6月25日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

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

本节从最直接的方法逐步优化,渐进探索了四种实现方式,并最终找到时间复杂度为O(N),辅助空间为常数的方案,内容如下:

==基本算法 使用Hash==

==DP方案==

==DP + Hash 方案==

==DP + Hash 优化方案==

==================================

基本算法 使用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);
}

==================================

DP方案

前面刚刚讨论过最长递增子序列的问题,咋一想就觉得二者有点类似,何不向DP方面想一下,为什么说二者类似,在LIS问题中,对于当前的元素,要么是与前面的LIS构成新的最长递增子序列,要么就是与前面稍短的子序列构成新的子序列或单独构成新子序列;

同理,对于最长不重复子串,某个当前的字符,如果它与前面的最长不重复子串中的字符没有重复,那么就可以以它为结尾构成新的最长子串;如果有重复,且重复位置在上一个最长子串起始位置之后,那么就与该起始位置之后的稍短的子串构成新的子串或者单独成一个新子串。

举个例子:例如字符串“abcdeab”,第二个字符a之前的最长不重复子串是“abcde”,a与最长子串中的字符有重复,但是它与稍短的“bcde”串没有重复,于是它可以与其构成一个新的子串,之前的最长重复子串“abcde”结束;

再看一个例子:字符串“abcb”,跟前面类似,最长串“abc”结束,第二个字符b与稍短的串“c”构成新的串;

这两个例子,可以看出些眉目:当一个最长子串结束时(即遇到重复的字符),新的子串的长度是与第一个重复的字符的下标有关的,如果该下标在上一个最长子串起始位置之前,则dp[i] = dp[i-1] + 1,即上一个最长子串的起始位置也是当前最长子串的起始位置;如果该下标在上一个最长子串起始位置之后,则新的子串是从该下标之后开始的

于是类似LIS,对于每个当前的元素,我们“回头”去查询是否有与之重复的,如没有,则最长不重复子串长度+1,如有,则考察上一个子串起始位置与重复字符下标的关系,当然,如果DP使用O(n^2)的方案,则我们只需在内层循环遍历到上一个最长子串的起始位置即可,如下。

O(N^2)的DP方案,我们可以与LIS的DP方案进行对比,是一个道理的。代码如下:

/* 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);
}

==================================

DP + Hash 方案

上面的DP方案是O(n^2)的,之所以是n^2,是因为“回头”去寻找重复元素的位置了,受启发于最初的Hash思路,我们可以用hash记录元素是否出现过,我们当然也可以用hash记录元素出现过的下标,既然这样,在DP方案中,我们何不hash记录重复元素的位置,这样就不必“回头”了,而时间复杂度必然降为O(N),只不过需要一个辅助的常数空间visit[256],典型的空间换时间。

代码如下:这样遍历一遍便可以找到最长不重复子串

/* 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;
                visit[arr[i]] = i; /* 更新最近重复位置 */
			}

		}
		if(dp[i] > maxlen)
		{
			maxlen = dp[i];
			maxindex = i + 1 - maxlen;
		}
	}
	output(arr);
}

==================================

DP + Hash 优化方案

写到这里,还是有些别扭,因为辅助的空间多了,是不是还能优化,仔细看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;
                visit[arr[i]] = i; /* 更新最近重复位置 */
			}
		}
		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));
}

本节相关代码可以到这里下载。

(全文完)

  • Tutu_Lux

    如果输入的字符集是Unicode……

    • Yx.Ac

      然后呢?

  • 庸男勿扰

    第三种dp+hash有问题吧,如果输入字符串是a,不会执行到for循环,没有更新maxlen,输出为0了

    • Yx.Ac

      恩,谢谢,这里是缺少了边界的检查,这里可以加一句

      if(NULL == arr)
      {
          maxlen = 0;
          output(arr);
      }
      

      然后程序中 maxlen=curlen=1;

  • xingzheHe

    其中指针p和pStart均是一直向前行进的(没有回溯),直到字符串结束,故其时间复杂度是:O(n)。欢迎讨论:)@xingzheHe

    • Yx.Ac

      嗯哪,明白了,谢谢!

  • xingzheHe

    楼主你好,利用hash就可以达到O(n)
    #include
    using namespace std;

    void GetMaxUnRepeatSubStr(char *str)
    {
    //global var
    int hashTable[256] ={0};
    char* pMS = str;
    int mLen = 0;

    //temp var
    char* pStart = pMS;
    int len = mLen;
    char* p = pStart;
    while(*p != '')
    {
    if(hashTable[*p] == 1)
    {
    if(len > mLen)
    {
    pMS = pStart;
    mLen = len;
    }

    while(*pStart != *p)
    {
    hashTable[*pStart] = 0;
    pStart++;
    len--;
    }
    pStart++;
    }
    else
    {
    hashTable[*p] = 1;
    len++;
    }
    p++;
    }
    // check the last time
    if(len > mLen)
    {
    pMS = pStart;
    mLen = len;
    }
    //print the longest substring
    while(mLen>0)
    {
    cout<<*pMS<<" ";
    mLen--;
    pMS++;
    }
    cout<<endl;
    }

    int main()
    {
    char* str1="bdabcdcf";
    GetMaxUnRepeatSubStr(str1);
    char* str2="abcdefb";
    GetMaxUnRepeatSubStr(str2);
    char* str3="abcbef";
    GetMaxUnRepeatSubStr(str3);

    return 0;
    }

    • Yx.Ac

      大赞啊~~谢谢 :-) ,我之前思考过两个指针的方法,不过就差一点点把hash再置空就可以了,哈哈

  • 远建

    if(visit[arr[j]] == 0)
    {
    visit[arr[j]] = 1;
    }
    else//这一点少考虑一种情况,如果最后一段字符串为最长的情况没考虑进去,如"abcdeabcedft"
    {
    if(j-i > maxlen)
    {
    maxlen = j - i;
    maxindex = i;
    }
    break;
    }

    • Yx.Ac

      您好,您说的情况代码已经考虑到了,如下这段便是:

      if((j == size) && (j-i > maxlen))
      {
      maxlen = j - i;
      maxindex = i;
      }

      您可以运行代码试试,可以正确输出,欢迎交流 :-)

  • Yx.Ac

    已勘误,谢谢啦,嘿!@Anderson

  • Anderson

    你好. 读了你的文章我觉得受益匪浅. 不过有个地方我觉得有点问题所以想和i你讨论讨论.最后一个DP+Hash的算法, 对于已经出现过的字符

    else
    {
    if(last_start <= visit[arr[i]])
    {
    curlen = i - visit[arr[i]];
    last_start = visit[arr[i]] + 1;
    visit[arr[i]] = i; /* 更新最近重复位置 */
    }else
    {
    ++curlen;
    }
    }

    在else后面, 只++了curlen, 但并没有更新重复位置. 比如是 cabccccc, 如果last_start指向a, 然后visit[/c] 则是0, 然后就会一直匹配ccccc. 这样会不会出问题?

  • Yx.Ac

    谢谢!:-) @sigma

  • sigma

    @Yx.Ac
    祝找工作顺利!

    • Yx.Ac

      非常感谢啦~!

  • Yx.Ac

    非常感谢二位!:-) ,指出一个大bug,由于原四种方法均有误,故我直接在原文勘误了,四种方法均已勘误,望验证。最近忙于找工作,勘误晚了些,望见谅,嘿,再次感谢!@sigma @abdrew

  • abdrew

    第二种DP代码中也有个bug,内层循环不应该到j>=0,而是到当前最长串的开始,可以是以下这组数据“acbabcd”。

  • sigma

    测试用例:abcaacdeabacdefg,四种方法结果均错误。不能单纯的考虑字符出现的位置,还要考虑上一次所求字符串的起始位置。

  • abdrew

    第一种Hash代码有bug,代码中maxlen更新应该放在外层循环而不是内层循环,否则当内层循环是因为j==size而跳出时,maxlen的值没有被改变,影响最终结果,具体的你可以试一下“ababcd”这组测试用例,你的程序结果为“ab”,正确结果明显是“abcd”,就是因为正确答案的内层循环是因为j==size跳出的,所以你的程序没有更新。