java实现字符串匹配
暴力匹配
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/** * 暴力匹配 * * @param str1 需要找的总字符串 * @param str2 需要找到的字符串 * @return 找到的字符串的下标 */private static int violence(String str1, String str2) { char[] s1 = str1.toCharArray(); char[] s2 = str2.toCharArray(); int s1Len = s1.length; int s2Len = s2.length; // 指针，分别指向两个字符串 int i = 0; int j = 0; // 保证匹配时不越界 while (i < s1Len && j < s2Len) { // 第一个字符匹配上了 if (s1[i] == s2[j]) { ++i; ++j; } else { i -= (j - 1); j = 0; } } // 判断是否成功 if (j == s2Len) { return i - j; } else { return -1;} |
KMP算法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
/** * KMP算法 * * @param str1 源字符串 * @param str2 子串 * @param next 匹配值表 * @return 对应下标，没有为-1 */private static int kmp(String str1, String str2, int[] next) { for (int i = 0, j = 0; i < str1.length(); ++i) { while (j > 0 && str1.charAt(i) != str2.charAt(j)) { j = next[j - 1]; } if (str1.charAt(i) == str2.charAt(j)) { j++; if (j == str2.length()) { return i - j + 1; } return -1;} * @return dest的部分匹配表private static int[] getkmpNext(String dest) { int length = dest.length(); int[] next = new int[length]; next[0] = 0; for (int i = 1, j = 0; i < length; i++) { while (j > 0 && dest.charAt(i) != dest.charAt(j)) { if (dest.charAt(i) == dest.charAt(j)) { next[i] = j; return next; |
到此这篇关于Java实现字符串匹配的文章就介绍到这了,更多相关java字符串匹配内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！
原文链接：https://www.cnblogs.com/coderDreams/p/16188698.html
