实现一算法：两个字符串 连续字符相同

Question

   有两个字符串，a和b， 实现一个算法，找出a,b中 连续相同的字符最多的那个字符串 
    如：String a = "abcdefghij"; String b="234efnmnghilsbwahah";   那么应该是：ghi     先说下算法如何实现，效率比较高一些，最好能有实现的代码，但最重要的是算法实现原理  谢谢大家~！~

Answer 1

package com.train.first;import java.lang.reflect.Method;
import java.util.ArrayList;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class Test
{
public static void main(String[] args) throws Exception
{
String str1 = "abcdefghij";
String str2 = "234efabcdenmnghilsbwahah";
String pstr = str1.length() < str2.length() ? str1 : str2;
String mstr = str1.length() < str2.length() ? str2 : str1;



int i = 0;
List<String> regex = getRegex(pstr, i);

out: while (regex != null)
{
for (int k = 0; k < regex.size(); k++)
{
Pattern p = Pattern.compile(regex.get(k));
Matcher m = p.matcher(mstr);

if (m.find())
{
System.out.println(regex.get(k));
break out;
}
}

regex = getRegex(pstr, ++i);
}
}

private static List<String> getRegex(String str, int i)
{
if (i >= str.length())
{
return null;
}

List<String> result = new ArrayList<String>();
result.add(str.substring(i));
result.add(str.substring(0, str.length() - i));

for (int k = i - 1; k > 0; k--)
{
result.add(str.substring(k, str.length() - (i - k)));
}

return  result;
}
}有些细节没有优化，只是简单的实现了功能

Answer 2

用KMP实现了下，对于楼主的输入比用正则能快到一个数量级。
如果字符最多的字符串有多个的话，只找第一个。
不过没怎么测试，先睡觉了。
public static void find(String string1, String string2) {
String string;
String pattern;
if (string1.length() > string2.length()) {
string = string1;
pattern = string2;
} else {
string = string2;
pattern = string1;
}
String find = null;
int maxLength = -1;
for (int i = 0; i < pattern.length(); i++) {
int[] result = KMPMatch(string, pattern.substring(i));
if (result[0] != -1 && result[1] > maxLength) {
find = string.substring(result[0], result[0] + result[1]);
maxLength = result[1];
}

}
System.out.println(find);
}

public static int[] KMPMatch(String string, String pattern) {
if (string == null || pattern == null || pattern.length() == 0)
return new int[]{-1, -1};
int maxIndex = -1;
int maxLength = -1;
int n = string.length();
int m = pattern.length();
int[] prefixs = new int[m];
computePrefix(pattern, prefixs);
for (int i = 0, q = 0; i < n; i++) {
while(q > 0 && pattern.charAt(q) != string.charAt(i))
q = prefixs[q-1];
if (pattern.charAt(q) == string.charAt(i)) {
q++;
if (q > maxLength) {
maxLength = q;
maxIndex = i - q +1;
}

}

if (q == m) {
maxLength = q;
maxIndex = i - q + 1;
break;
}
}
return new int[]{maxIndex, maxLength};
}

public static void computePrefix(String pattern, int[] prefixs) {
prefixs[0] = 0;
for (int i = 1, k = 0, length = pattern.length(); i < length; i++) {
while(k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
k = prefixs[k];
}
if (pattern.charAt(k) == pattern.charAt(i))
k++;
prefixs[i] = k;
}
}

Answer 3

public class Test { public static void main(String[] args) {
String a = "abcdefghij"; 
String b = "234efnmnghilsbwahah";
System.out.println(getSameString(a, b));
}

private static String getSameString(String s1, String s2) {
int startPos = 0; //始终指向重复字符串的起始位置
int endPos = 0; //要截取字符串的末尾
String str1 = null; //始终存储当前重复字符最多的那个字符串
String str2 = null; //存储了当前重复的字符串
int index = 0; //遍历字符串的指针
// int j = 0; //记录每次出现重复字符的起始位置
for(int i=0; i<s1.length(); i++) {
char c = s1.charAt(i);
while((index=s2.indexOf(c,index)) != -1) {
startPos = index;
endPos = startPos + 1;
int m = i + 1; //m代表了前一个重复字符串的后一个位置
while(index < s2.length()-1 && 
m < s1.length() &&
s1.charAt(m) == s2.charAt(index+1)) {
endPos ++; //如果有字符相等，则endPos后移一位
m++; //相应的字符串s1也后移下
index++; //游标后移
}
index++;
str2 = s2.substring(startPos, endPos);
if(str1 == null || str1.length() < str2.length())
str1 = str2;
}
}
return str1;
}
}

Answer 4

public class Testst { public static void main(String[] args) {
String st1 = "abcdhyum";
String st2 = "ascdhg";
String Max = "" ;
for(int i =0;i<st1.length();i++){
for(int j = i ; j <st1.length();j++){
String sub = st1.substring(i,j); 
if((st2.indexOf(sub)!=-1)&&(sub.length()>Max.length())){
Max = sub;
}
}
}
System.out.println(Max); }}//输出结果是：cdh

Answer 5

看了一下  说一下大体思路
    首先从a 从第一个字母开始  然后跟b 里的字母去比较
      找到相同的  则 a和b的相邻的第二个字母  如果相同继续比较  然后把相同的字符串记录下来否则 从a的第二个字母开始  比较     
这也是最笨的算法了

Answer 6

  
package test;public class T { /**
 * 程序思想是从较短串中(这里是a)尽量取最长的串和b比
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
String a="abcdefghij";
String b="234efnmnghilsbwahah";
int minlength=a.length()<=b.length()?a.length():b.length();//得到两者中长度短的串,这里是a串
String cmp=a.length()<=b.length()?a:b;//得到较短的串,这里是a
String tocmp=a.length()>b.length()?a:b;//得到较长的串,这里是b
for(int i=minlength-1;i>=0;i--){
int cmplen=minlength-i;//比较次数(a中长度为i+1的串和b比较次数)
for(int j=0;j<=cmplen-1;j++){
String str=cmp.substring(j,minlength-cmplen+1+j);//循环cmplen次去和b比较
if(tocmp.indexOf(str)!=-1){//利用String类中方法看b中是否有连续的串
System.out.println(a+"和"+b+"中连续相同的字符最多的那个字符串是:"+str);//有则打印,退出程序
System.exit(0);
}
}
}
System.out.println("两者没有串匹配!!");
}}

Answer 7

答：典型的使用KMP算法来解决的问题。支持！