给定一个字符串,求出其最长的重复子串。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

//给定一个字符串,求出其最长的重复子串
//方法一
string lsubstr_1(const string & str)
{ 
	vector<string> vs;
	for (int i = 0; i < str.size(); i++)
		vs.push_back(str.substr(i));
	sort(vs.begin(), vs.end());
	int max = 0;
	int flag = 0;
	for (int i = 0; i <( vs.size()-1); i++)
	{
		int j = 0;
		while (vs[i][j] == vs[i + 1][j] && j<vs[i].size() && j<vs[i+1].size())
			j++;
		if (j>max)
		{
			max = j;
			flag = i;
		}			
	}
	return vs[flag].substr(0, max);
}

//方法二
string lsubstr_2(const string & str)
{
	string maxstr;
	for (int i = 0; i < str.size();i++)
	for (int j = (str.size() - i); j >=1 ; j--)
	{
		string subs = str.substr(i, j);
		int front = str.find(subs);
		int back = str.rfind(subs);
		if (front != back && subs.size() > maxstr.size())
			maxstr = subs; 
	}
	return maxstr;
}

//方法三
string lsubstr_3(const string & str)
{
	string maxstr;
	for (int i = 0; i < str.size(); i++)
		for (int j = 0; j < i; j++)
		{
			string temp;
			int k = j;
			int m = i;
			while (str[m] == str[k] && i<str.size() && k<str.size())
			{
				m++; k++;
			}
			temp = str.substr(j, k - j);
			if (temp.size()>maxstr.size())
				maxstr = temp;
		}
	return maxstr;
}

void main(void)
{
	string test;
	//cin >> test;
	getline(cin, test);
	cout << lsubstr_1(test) << endl;
	cout << lsubstr_2(test) << endl;
	cout << lsubstr_3(test) << endl;
}

string FindStr(const string &str)
{
	string temp, MaxStr;
	int MaxLen = 0;
	for (int i = 0; i < str.length(); ++i)
	{
		for (int j = str.length() -i; j != 0; --j)
		{
			temp = str.substr(i, j);
			int front = str.find(temp);
			int behind = str.rfind(temp);
			int templen = temp.length();
			if (front != behind&&templen > MaxLen)
			{
				MaxStr = temp;
				MaxLen = templen;
			}
		}
	}
	return MaxStr;
}

public class MaxReStr {
	public String findStr(String s){
		if(s==null){
			return null;
		}
		//最长重复子串的长度
		int max=0;
		//最长重复子串的第一个字符在s中的下标
		int first=0;
		String res = null;
		//i为每次循环设定的字符串比较间隔：1,2，...，s.length()-1
		for(int i=1;i<s.length();i++){
			for(int k=0,j=0;j<s.length()-i;j++){
				if(s.charAt(j)==s.charAt(j+i))
					k++;
				else
					k=0;
				if(k>max){
					max=k;
					first=j-max+1;
				}
			}
			if(max>0){
				res = s.substring(first, first+max);
			}
		}
		return res;
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String s = "eabcdabcf";
		System.out.println(new MaxReStr().findStr(s));
	}
}

#include <stdlib.h>
#include <stdio.h>

#define MaxChar 5000
char a[MaxChar];
char *post[MaxChar];

int pstrcmp(const void *p1, const void *p2)
{
    return strcmp(*(char* const *)p1, *(char* const *)p2);
}

//求排序后相邻两个串的最长公共前缀
int common_len(char *p, char *q)
{
    int k = 0;
    while(*p && (*p++ == *q++))
        k++;
    return k;
}

int main()
{
    char ch;
    int i = 0, j;
    int temp;
    int max = 0, max_index = 0;
    while((ch = getchar()) != '\n')
    {
        post[i] = &a[i];//将后缀式的指针指向该后缀式的第一个字符
        a[i++] = ch;
    }
    a[i] = '\0';

    qsort(post, i, sizeof(char *), pstrcmp);//对所有后缀式进行排序

    for(j = 0; j < i - 1; j++)
    {
        temp = common_len(post[j], post[j+1]);
        if(max < temp)
        {
            max = temp;
            max_inde敏感词rintf("%d %s\n", max, post[max_index]);
    return 0;
}

O(n^3)

#include <iostream>
#include <string>
using namespace std;
int main(){
    string s;
    cin >> s;
    int len = 0;
    for(int i = 0; i < s.size(); i++){
        for(int j = s.size()-i; j >= i; j--){
            string str = s.substr(i, j);
            int front = s.find(str);
            int back = s.rfind(str);
            if(front != back && j > len){
                len = j;
            }
        }
    }
    cout << len << endl;
    return 0;
}

string longestRepeatStr(string str) {
    int n = str.length();
    for(int i = n - 1; i > 0; --i)
         for(int j = 0; j < n; ++j) {
             if(i + j < n) {
                string cur = str.substr(j,i);
                int index1 = str.find(cur); // 从前往后找
                int index2 = str.rfind(cur); // 从后往前找
                if(index1 != index2)
                    return cur;
            }
        }
}

int longest = 0;
int currentLongest = 0;
for(int i = 1; i < array.size();i++){
    if(array[i]==array[i-1]){
        currentLongest++;
    }
    else{
        currentLongest = 0;
    }
    if(currentLongest >= longest)
    {
        longest = currentLongest;
    }
}

return longest;

下面说明为什么(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数:
首先rand7()-1得到一个离散整数集合{0，1，2，3，4，5，6}，其中每个整数的出现概率都是1/7。那么(rand7()-1)*7得到一个离散整数集合A={0，7，14，21，28，35，42}，其中每个整数的出现概率也都是1/7。而rand7()得到的集合B={1，2，3，4，5，6，7}中每个整数出现的概率也是1/7。显然集合A和B中任何两个元素组合可以与1-49之间的一个整数一一对应，也就是说1-49之间的任何一个数，可以唯一确定A和B中两个元素的一种组合方式，反过来也成立。由于A和B中元素可以看成是独立事件，根据独立事件的概率公式P(AB)=P(A)P(B)，得到每个组合的概率是1/7*1/7=1/49。因此(rand7()-1)*7+rand7()生成的整数均匀分布在1-49之间，每个数的概率都是1/49。

程序：

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;

int main()
{
	freopen("test.txt", "r", stdin);

	string str;
	while(cin>>str)
	{
		string maxStr;
		for(int i = 0; i < str.size(); i++)
		{
			for(int j = (str.size() - i); j >= 1; j--)
			{
				string subStr = str.substr(i, j);
				int start = str.find(subStr);
				int end = str.rfind(subStr);

				if(start + subStr.size() <= end && maxStr.size() < subStr.size())
					maxStr = subStr;
			}
		}
		cout<<maxStr<<endl;
	}
	return 0;
}

string findString( string& s ){

	if( s.length() < 2 )
		return s;

	int index = 0;

	string res;
	int maxLen = 0;
	int len = s.length();

	for ( ; index<len-1; ++index ) {

		int j = index+1;

		while( s[index] != s[j] && j<len )
			++j;

		int count = 0;
		string tmp;

		if( j!=len ){

			int i = index;

			while( s[i] == s[j] ){

				++count;
				tmp.push_back( s[i] );
				++i; 
				++j;
			}

			if( count>maxLen ){

				maxLen = count;
				res.swap( tmp );
				tmp.clear();
			}
		}
	}

	return res;
}