• 字符串匹配问题

  • 常见的字符串匹配算法包括暴力匹配、 Knuth-Morris-Pratt 算法、Boyer-Moore算法、Sunday 算法等 

• 解题 思路 1:
  • 两个指针各指向两个字符串的起始位置,先判断,两个字符串的第一个字符是否相同,如果相同的话,则将两个指针往下移动,并且判断较短字符串的下一个字符是否为空,如果为空,直接返回事先声明的index角标,如果不相等的话,则将较短指针的指向置为初始位置,将较长字符串的指向 = 上一次起始的角标 + 1,再将上一次起始的角标加一进行更新

class Solution {
public:int strStr(string haystack, string needle) {int p1=0,p2=0;int index = 0;while(p1 < haystack.length()){if(needle[p2] ==  haystack[p1]){if(needle[p2+1] == '\0') {return index;}p2++;p1++;}else{p2 = 0;p1 = index+1;index++;}}return -1;}
};

解法 思路 2:

• 思路及算法

  我们可以让字符串needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。

  为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1。

class Solution {
public:int strStr(string haystack, string needle) {int n = haystack.size(), m = needle.size();for (int i = 0; i + m <= n; i++) {bool flag = true;for (int j = 0; j < m; j++) {if (haystack[i + j] != needle[j]) {flag = false;break;}}if (flag) {return i;}}return -1;}
};