在字符串中查找最长重复子串
如何在字符串中查找最长重复子串？比如字符串"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++;intk=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))//相等则字符个数加1lcount++;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;}
。