字符串匹配问题
给定一个主串（以 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 }