字符串匹配问题
给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。
解决这种类型的问题的两种方法
1、常规暴力解法 2、KMP算法(及优化方法)
C++实现
1 #include <stdio.h>
2 #include <iostream>
3 #include <algorithm>
4 #include <vector>
5 using namespace std;
6
7 /**
8 * KMP：
9 * 给定一个主串（以 S 代替）和模式串（以 P 代替），要求找出 P 在 S 中出现的位置，此即串的模式匹配问题。
10 */
11
12 class Solution {
13
14 private:
15
16 public:
17
18 /**
19 * 暴力解法
20 * @param s ：主串
21 * @param p ：模式字符串
22 * @return
23 */
24 int bruteForce(
string s,
string p) {
25 int i =
0;
26 int j =
0;
27 int lengthOfS =
s.size();
28 int lengthOfP =
p.size();
29
30 while (i < lengthOfS && j <
lengthOfP) {
31 if (s[i] ==
p[j]){
32 i++
;
33 j++
;
34 }
else {
35 i = i-j+
1;
36 j =
0;
37 }
38 }
39
40 if (j ==
lengthOfP) {
41 return i-
j;
42 }
43
44 return -
1;
45 }
46
47 /**
48 * 求解模式串的每个位置的相同真前后缀
49 * @param pattern：模式字符串
50 * @param next ：模式串的每个位置的相同真前后缀长度
51 */
52 int * getNext(
string pattern) {
53 int* next =
new int[
100]{
0};
54 int patternSize =
pattern.size();
55 int i =
0,j = -
1;
56 next[
0] = -
1;
57
58 while(i <
patternSize) {
59 if (j == -
1 || pattern[i] ==
pattern[j]) {
60 i++
;
61 j++
;
62 next[i] =
j;
63 }
else {
64 j =
next[j];
65 }
66 }
67 return next;
68 }
69
70 /**
71 * KMP implementation
72 * @param s
73 * @param p
74 * @param next
75 * @return
76 */
77 int KMP(
string s,
string p) {
78 int* next =
getNext(p);
79 int i =
0;
80 int j =
0;
81 int lengthOfS =
s.size();
82 int lengthOfP =
p.size();
83
84 while(i < lengthOfS && j <
lengthOfP) {
85 if(j == -
1 || s[i] == p[j]) {
// P 的第一个字符不匹配或 S[i] == P[j]
86 i++
;
87 j++
;
88 }
else {
89 j =
next[j];
90 }
91 }
92
93 if (j ==
lengthOfP) {
94 return i-
j;
95 }
96 return -
1;
97 }
98
99 };
100
101 int main() {
102 string s,p;
103 getline(cin,s);
104 getline(cin,p);
105 Solution newSolution;
106 cout << newSolution.KMP(s,p) <<
endl;
107
108 }
转载于:https://www.cnblogs.com/TonvyLeeBlogs/p/9472899.html
相关资源：KMP算法（C 实现）
