在字符串中查寻最长重复子串

在字符串中查找最长重复子串

       如何在字符串中查找最长重复子串？比如字符串"abcdtttabcd"的最长重复子串为“abcd”，"cabcabca"的最长重复字串为“cabca”，"cabcabcacabcabca"的最长重复字符串为“cabcabca”。

分析：

        重复子串的起始位置如何？如果子串1的开始位置为i，那么子串1的重复子串（设为子串2）的开始位置最小为i+1。变量i从0开始遍历字符串，对于每个变量i变量j从i+1开始遍历。比较字符是否相等，如果相等字符记数增加1。根据贪心算法的原则进行了一些优化。

std::string  LCS_LENGTH_SIMPLE(std::string strX)
{
	int m=strX.length();
	int lcs=0;
	int npos=-1;

	for(int i=0;i<m;i++)//i从0开始
		{
			int lcount=0;
			for(int j=i+1;j<m;j++)//对于每个i，j从i+1开始
		{
			 lcount=0;

			if(strX.at(i)==strX.at(j))//如果字符相等
			{
				lcount++;		
				int	k=std::min(m-i-1,m-j-1);//位置i和j到字符串结尾的最小字符数

				for(int t=1;t<=k;++t)//判从相等的字符往后再进行比较
					{
						if(strX.at(i+t)==strX.at(j+t))//相等则字符个数加1
						lcount++;
						else
						{
							
							break;
						}
				    }

				//记录最大重复字符串的位置和字符个数
				if(lcs<lcount)
					{
						lcs=lcount;
						npos=i;
				   }


			      j=j+lcount-1;//优化，开始从新的位置寻找
			}
		}

			if(lcount>0)
			i=i+lcount-1;//优化，开始从新的位置寻找
	
	}
		std::string str;
		if(lcs>0)
			str=strX.substr(npos,lcs);


		return str;
}

。