1 算法思想
1.1 思路
解决问题:当主串中第 i 个字符与模式中第 j 个字符失配(即比较不相等)时,主串中第 i 个字符(i 指针不回溯)应与模式中哪个字符再比较。
-
next[j]:模式中第 j 个字符失配时,在模式中重新与主串比较的字符位置(最长公共前后缀长度+1,下标从 1 开始)
\text { next }[j]=\left\{\begin{array}{ll}
0 & \text { 当 } j=1 \text { 时 } \\
\operatorname{Max}\left\{k \mid 1
-
计算next数组:仅取决于模式串本身而和相匹配的主串无关
- 仿照kmp算法,如果p[j]!=p[next[j]],那么next[j+1]的可能次大值为next[next[j]]+1,依次类推即可高效求出next[j+1]
-
若在匹配过程中si=pj,则 i 与 j 分别增 1;
-
否则,i 不变,j 退至 next[j] 的位置再比较;若 j 退到值为 0(即模式串的第一个字符失配),则从主串的下一个字符si+1起与模式串重新开始匹配;
-
重复执行step3、step4,直至结束。
1.2 优化
修正next数组,next[j]=k,若模式中p[j]=p[k],则next[j]=next[k]
1.3 算法分析
- 时间复杂度:O(m+n)
- 空间复杂度:next数组,O(m)
2 代码实现
2.1 C++
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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| #include <iostream> typedef long long ll; using namespace std;
const int maxn = 1e4; int next2[maxn]; int nextval[maxn];
void get_next(string p) { int i = 1, j = 0; next2[1] = 0; while (i < p.size()) { if (j == 0 || p[i] == p[j]) { i++; j++; next2[i] = j; } else { j = next2[j]; } } }
void get_nextval(string p) { int i = 1, j = 0; nextval[1] = 0; while (i < p.size()) { if (j == 0 || p[i] == p[j]) { i++; j++; if (p[i] != p[j]) nextval[i] = j; else nextval[i] = nextval[j]; } else { j = nextval[j]; } } }
int kmp(string s, string p) { get_nextval(p); int i = 0, j = 1; while (i < s.size() && j < p.size()) { if (j == 0 || s[i] == p[j]) { i++; j++; } else { j = nextval[j]; } } if (j >= p.size()) return i - p.size() - 1; else return 0; } int main() { std::ios::sync_with_stdio(false); string s = " acabaabaabcacaabc", t = " abaabcac"; cout << kmp(s, t);
return 0; }
|
2.2 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 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
| class KMP { private int maxn = 1000; private int[] next = new int[maxn]; private int[] nextval = new int[maxn]; public KMP() { } public void get_next(String p) { int i = 1, j = 0; next[1] = 0; while (i < p.length()) { if (j == 0 || p.charAt(i) == p.charAt(j)) { i++; j++; next[i] = j; } else { j = next[j]; } } } public void get_nextval(String p) { int i = 1, j = 0; nextval[1] = 0; while (i < p.length() - 1) { if (j == 0 || p.charAt(i) == p.charAt(j)) { i++; j++; if (p.charAt(i) != p.charAt(j)) nextval[i] = j; else nextval[i] = nextval[j]; } else { j = nextval[j]; } } } public int kmp(String s, String p) { get_nextval(p); int i = 0, j = 1; while (i < s.length() && j < p.length()) { if (j == 0 || s.charAt(i) == p.charAt(j)) { i++; j++; } else { j = nextval[j]; } } if (j >= p.length()) return i - p.length() - 1; else return 0; } } public class test1 { public static void main(String[] args) { KMP test = new KMP(); String s = " acabaabaabcacaabc", t = " abaabcac"; System.out.println(test.kmp(s, t)); } }
|
3 参考