有两个字符串，a和b， 实现一个算法，找出a,b中 连续相同的字符最多的那个字符串
如：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>(); 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; }}
------解决方案--------------------
用KMP实现了下，对于楼主的输入比用正则能快到一个数量级。
如果字符最多的字符串有多个的话，只找第一个。
不过没怎么测试，先睡觉了。
- Java code
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; } }