a*******8
发帖数: 110 | 1 给两个String, s1和s2，找s1的尾部和s2的头部的最长match
Example:
s1: "1234", s2: "3451", result: "34"
s1: "12", s2: "123", result: "12"
If s1.length() == m and s2.length() == n,
k = Math.min(m, n), can you find a solution better than O(k^2)? | v****c
发帖数: 29 | 2 这不就是KMP算法吗，O(k)
s2作为pattern去match s1
【在 a*******8 的大作中提到】
: 给两个String, s1和s2，找s1的尾部和s2的头部的最长match
: Example:
: s1: "1234", s2: "3451", result: "34"
: s1: "12", s2: "123", result: "12"
: If s1.length() == m and s2.length() == n,
: k = Math.min(m, n), can you find a solution better than O(k^2)?
| a*******8
发帖数: 110 | 3 O(k^2)的brute force算法附上：
String getCommon(String s1, String s2) {
int m = s1.length();
int n = s2.length();
int maxLength = Math.min(m, n);
while (maxLength > 0) {
if (s1.substring(m - maxLength).compareTo(s2.substring(0,
maxLength)) == 0) {
return s1.substring(m - maxLength);
}
--maxLength;
}
return "";
} | Z*****Z
发帖数: 723 | 4 public static void main(String[] args) {
System.out.println(getCommon("1234", "3451"));
System.out.println(getCommon("12", "123"));
System.out.println(getCommon("123", "12"));
System.out.println(getCommon("12", "12"));
}
static String getCommon(String s1, String s2) {
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
int[] failure = buildFailureTable(arr2);
int i = -1, j = -1;
if(arr2.length < arr1.length){
i = arr1.length - arr2.length;
}
while(i < arr1.length - 1){
i ++;
j ++;
while(j >= 0 && arr1[i] != arr2[j]){
j = failure[j];
}
}
if(j <= 0){
return "";
}
return s2.substring(0, j+1);
}
private static int[] buildFailureTable(char[] arr) {
int[] table = new int[arr.length + 1];
int i = -1, j = 0;
table[0] = -1;
while(j < arr.length - 1){
while(i >= 0 && arr[i] != arr[j]){
i = table[i];
}
i ++;
j ++;
if(arr[i] == arr[j]){
table[j] = table[i];
} else {
table[j] = i;
}
}
return table;
}
【在 a*******8 的大作中提到】
: O(k^2)的brute force算法附上：
: String getCommon(String s1, String s2) {
: int m = s1.length();
: int n = s2.length();
:
: int maxLength = Math.min(m, n);
: while (maxLength > 0) {
: if (s1.substring(m - maxLength).compareTo(s2.substring(0,
: maxLength)) == 0) {
: return s1.substring(m - maxLength);
| h****t
发帖数: 184 | 5 给点解释吧..
【在 Z*****Z 的大作中提到】
: public static void main(String[] args) {
: System.out.println(getCommon("1234", "3451"));
: System.out.println(getCommon("12", "123"));
: System.out.println(getCommon("123", "12"));
: System.out.println(getCommon("12", "12"));
: }
: static String getCommon(String s1, String s2) {
: char[] arr1 = s1.toCharArray();
: char[] arr2 = s2.toCharArray();
: int[] failure = buildFailureTable(arr2);
| C***U
发帖数: 2406 | 6 赞同
【在 v****c 的大作中提到】
: 这不就是KMP算法吗，O(k)
: s2作为pattern去match s1
| Z*****Z
发帖数: 723 | 7 见vimabc回复
【在 h****t 的大作中提到】
: 给点解释吧..
| p*****2
发帖数: 21240 | 8
白芷你太帅了。KMP算法我从来没研究过。面试会考吗？
【在 Z*****Z 的大作中提到】
: public static void main(String[] args) {
: System.out.println(getCommon("1234", "3451"));
: System.out.println(getCommon("12", "123"));
: System.out.println(getCommon("123", "12"));
: System.out.println(getCommon("12", "12"));
: }
: static String getCommon(String s1, String s2) {
: char[] arr1 = s1.toCharArray();
: char[] arr2 = s2.toCharArray();
: int[] failure = buildFailureTable(arr2);
| Z*****Z
发帖数: 723 | 9 应该不会吧。。。
这个kmp主要觉得思想很巧。我一边看一边膜拜knuth。。。
不过leetcode上不是有个strstr的题么
【在 p*****2 的大作中提到】
:
: 白芷你太帅了。KMP算法我从来没研究过。面试会考吗？
| p*****2
发帖数: 21240 | 10
那题BF就可以了。
【在 Z*****Z 的大作中提到】
: 应该不会吧。。。
: 这个kmp主要觉得思想很巧。我一边看一边膜拜knuth。。。
: 不过leetcode上不是有个strstr的题么
| l*********u
发帖数: 19053 | 11 俺半路出家，不会算法。请问各位用俩pointer算，会有什么问题捏？俺的理解，移动
pointer很快的。
p１指向１２３４的４，p２指向３４５１的３
移动p２，找到４
同时向回移动p１，p２，直到指向char不等
得到３４。
【在 a*******8 的大作中提到】
: 给两个String, s1和s2，找s1的尾部和s2的头部的最长match
: Example:
: s1: "1234", s2: "3451", result: "34"
: s1: "12", s2: "123", result: "12"
: If s1.length() == m and s2.length() == n,
: k = Math.min(m, n), can you find a solution better than O(k^2)?
| h*****3
发帖数: 1391 | 12 好像有点问题。
如果是123434， 343451呢？
找哪个4？
【在 l*********u 的大作中提到】
: 俺半路出家，不会算法。请问各位用俩pointer算，会有什么问题捏？俺的理解，移动
: pointer很快的。
: p１指向１２３４的４，p２指向３４５１的３
: 移动p２，找到４
: 同时向回移动p１，p２，直到指向char不等
: 得到３４。
| l*********u
发帖数: 19053 | 13 说的没错，pointer看来不行。
比如123434， 2343451/342343451
【在 h*****3 的大作中提到】
: 好像有点问题。
: 如果是123434， 343451呢？
: 找哪个4？
| a*******8
发帖数: 110 | 14 面试时的String match题，如果要求比brute force更好的解的话，都可以考虑这个。
看了半天Wiki，才弄明白。。。
//KMP algorithm
//Reference WIKI: //http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
String getCommon(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
int[] table = buildFailureTable(s2, maxLength);
int m = s1.length() - maxLength;
int i = 0;
while (m + i < s1.length()) {
if (s1.charAt(m + i) == s2.charAt(i)) {
//match found
if (m + i == s1.length() - 1)
return s1.substring(m);
++i;
} else {
//mismatch
m = m + i - table[i];
i = (table[i] > 0 ? table[i] : 0);
}
}
return "";
}
int[] buildFailureTable(String s, int k) {
int[] table = new int[k];
if (k == 0)
return table;
table[0] = -1;
for (int i = 2; i < k; ++i) {
if (s.charAt(i - 1) == s.charAt(table[i-1]))
table[i] = table[i-1] + 1;
}
return table;
} |
|
