我要招人

去企业版

首页 > 试题广场 >

输入一个字符串，如何求最大重复出现的字符串呢？比如输入tta

[问答题]

输入一个字符串，如何求最大重复出现的字符串呢？比如输入ttabcftrgabcd,输出结果为abc，canffcancd,输出结果为can。

查看答案及解析

推荐

卐当之用

string FindString(string str)
{
    string tep,postep;
    int len=0;
    for(int i=0;i<str.length();i++)
    {
        for(int j=str.length()-1;j>1;j--)
        {
            if(j+i<str.length())
            {
                tep=str.substr(i,j);
            int front=str.find(tep);//从前往后找，找到的第一个字符所在整个字符串中的位置（从0开始的）
            int behind=str.rfind(tep);//从后往前找。。。。。
            int teplen=tep.length();
            if(front!=behind && teplen>=len)
            {
                len=teplen;
                postep=tep;
            }
            }
            
        }
    }

    return postep;
}

编辑于 2015-06-19 20:56:17 回复(0)

=蛇=

我想问如果像ABCDEFG 这种字符串。。都只重复一次，算谁的

发表于 2015-07-21 11:29:41 回复(0)

everbird

#!/usr/bin/env python
# encoding: utf-8


def find(s):
    array = suffixs(s)
    array.sort()
    r = ''
    max_r = 0
    for i in range(len(array)-1):
        a = array[i]
        b = array[i+1]
        lens = min(len(a), len(b))
        cnt = 0
        for j in range(lens):
            if a[j] == b[j]:
                cnt += 1
        if max_r < cnt:
            max_r = cnt
            r = a[:cnt]

    return r


def suffixs(s):
    return [s[i:] for i in range(len(s))]


if __name__ == '__main__':
    print find('canffcancd')
    print find('ttabcftrgabcd')

编程珠玑中后缀数组的解法

发表于 2015-06-19 01:33:42 回复(0)

chalson

不能保证正确性，仅仅是记录一下
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<string>init(string s)//生成后缀数组
{
	vector<string> back;
	for (int i = 0; i < s.size(); ++i)
	{
		string t = "";
		t = s.substr(i, s.size() - i);
		back.push_back(t);
	}
	return back;
}

string mycompare(string a, string b)
{
	string t = "";
	for (int i = 0; i < a.size() && i < b.size(); ++i)
	{
		if (a[i] == b[i])
			t += a[i];
		else
			break;
	}
	return t;
}

string process(vector<string>& ss)
{
	string max_string = "";
	sort(ss.begin(), ss.end());
	for (int i = 1; i < ss.size(); ++i)
	{
		string back=mycompare(ss[i - 1], ss[i]);
		if (back.size() > max_string.size())
			max_string = back;

	}
	return max_string;
}



int main()
{
	vector<string> rr;
	rr = init("aabc");
	/*for (string val : rr)
		cout << val << endl;*/
	cout << process(rr) << endl;

	return 0;
}

发表于 2021-08-27 22:01:09 回复(0)

塞上长城

可以用前缀数组

发表于 2015-08-09 23:58:16 回复(0)

太阳光

javascript:

function getStr(str){
  for(var i = Math.ceil(++str.length /2);i--;){
    if(str.match(new RegExp("(\\w{"+i+"}).*\\1+","g")))return RegExp.$1;
  }
}
alert(getStr("ttabcftrgabcd"));

编辑于 2015-06-25 14:43:59 回复(0)

小菜一枚

const int maxcharnum = 5000000;
bool StrCmp(char *str1,char *str2)
{
if(strcmp(str1,str2)>=0)
  return false;
else
  return true;
}
void getsuffixarray(char *str,char *suffixstr[]) //求取字符串的所有后缀字符串
{
int len = strlen(str);
for(int i = 0 ; i <len;i++)
{
  suffixstr[i] = &str[i];
}
}
int getstrlen(char *str1,char *str2)  //获取字符串相等的长度
{
int len = 0;
while(*str1&&*str2&&*str1++ == *str2++)
   len++;
return len;
}
void getmaxrestr(char *str)
{
int len = strlen(str);
int conreslen = 0;
int maxloc = 0;
int maxlen = 0;
char *suffixstr[maxcharnum];
getsuffixarray(str,suffixstr);
sort(suffixstr,suffixstr+len,StrCmp);//排序

for(int i = 0 ;i < len-1;i++)
{
  conreslen = getstrlen(suffixstr[i],suffixstr[i+1]);
  if(maxlen < conreslen)
  {
   maxloc = i;
   maxlen = conreslen;
  }
}
for(int j = 0 ;j < maxlen;j++)
{
  cout<<suffixstr[maxloc][j];
}
cout<<endl;
}

这题使用字符串的后缀来计算，然后将所有后缀按字符串大小排序，再依次比较，得到最长的相同字符即可，程序如上

发表于 2015-06-19 17:25:12 回复(0)

王一凡

动态规划怎么样？求字符串和自身的最长公共子串，设定子串不可以有共同的终点。

发表于 2015-06-19 11:08:05 回复(0)

日来来

public int lengthOfLongestSubstring(String s) {
int runner=0,walker=0;
HashMap<Character,Integer> map = new HashMap<>();
int max=0;
while(runner<s.length()) {
char c = s.charAt(runner);
Integer i = map.get(c);
if(i==null)
map.put(c,runner);
else if(i>=walker){
int l = runner-walker;
max = l>max?l:max;
walker=i+1;
map.put(c,runner);
}
else
map.put(c,runner);
runner++;
}
int l = runner-walker;
max = l>max?l:max;
return max;
}

发表于 2015-06-19 08:46:49 回复(0)

欧阳

使用hash表，线性时间

发表于 2014-10-14 18:32:09 回复(1)

提交观点

问题信息

动态规划亚马逊

上传者：kington

难度：

10条回答 11收藏 10834浏览

输入一个字符串，如何求最大重复出现的字符串呢？比如输入tta

问题信息

热门推荐

相关试题