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

www.MyException.Cn  网友分享于：2013-01-17  浏览：86次

如：String a = "abcdefghij"; String b="234efnmnghilsbwahah"; 那么应该是：ghi

先说下算法如何实现，效率比较高一些，最好能有实现的代码，但最重要的是算法实现原理 谢谢大家~！~

------解决方案--------------------
Java code
```
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>();

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

return  result;
}
}
------解决方案--------------------用KMP实现了下，对于楼主的输入比用正则能快到一个数量级。如果字符最多的字符串有多个的话，只找第一个。不过没怎么测试，先睡觉了。Java codepublic 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;
}
}
```