2 tommypdl tommypdl 于 2014.12.07 14:52 提问

字符串中最长出现至少2次的子串

一个Java源文件,类名为RepeatSubstring,其中public static int FindMax(String S)函数为算法执行的函数。

题目内容: 作为依依的好朋友,技术男沛沛在依依生日时送给他一个超长字符串 S 。沛沛要依依在其中找出一个最长的字符串 T ,使得 T 在 S 中至少出现了两次,而他想说的秘密就藏在 T 中。
由于字符串实在是太长了,依依总是找不到合适的 T 。于是依依请你帮他找到这个 T 的长度。

【输入格式】
一行。一个字符串,即题目中说的S 。

【输出格式】
一行。一个整数,表示最长的 T 的长度。

【样例输入】
ababa

【样例输出】
3

「数据范围」
对于 30% 的数据,S长度 <= 100
对于 60% 的数据,S长度 <= 8000
对于 100% 的数据,S长度 <= 50000

3个回答

caozhy
caozhy   Ds   Rxr 2014.12.07 15:21

一样的问题:http://ask.csdn.net/questions/156615

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
string s = "依依我不爱你还能爱谁,依依我不爱你才怪";
var query = Enumerable.Range(0, s.Length).Select(x => s.Substring(x)).OrderBy(x => x).ToArray();
int idx = 0; int max = 0;
for (int i = 1; i < query.Length; i++)
{
int same = query[i].Zip(query[i - 1], (x, y) => x == y).TakeWhile(x => x).Count();
if (same > max)
{
idx = i; max = same;
}
}
Console.WriteLine(query[idx].Substring(0, max));
Console.WriteLine(query[idx].Substring(0, max).Length);
}
}
}

q107770540
q107770540   Ds   Rxr 2014.12.07 16:40

同样的问题为何问2遍?

tommypdl
tommypdl   2014.12.22 12:32

public class RepeatSubstring {

/**
 * @param args
 * author:lao ban sha bi
 */

public static int FindMax(String S){
    long startTime = System.currentTimeMillis();
    int Length=S.length();
    String A=null,B=null;
    int MAX=0,max=1;
    for(int a=0;a<Length;a++){
        max=MAX+1;
        for(int b=a+1;b<Length;b++){
            if(b+max>Length) break;
            A=S.substring(a, a+max);
            B=S.substring(b, b+max);
            if(A.equals(B))
            {
                if(MAX<max){
                    MAX=max;
                }
                b--;
                max++;
            }
        }
    }
    long endTime = System.currentTimeMillis();
    System.out.println((endTime-startTime)+"ms");
    return MAX; 
}

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner s = new Scanner(System.in);
    String str = s.next();
    System.out.println(FindMax(str));
}

}

Csdn user default icon
上传中...
上传图片
插入图片