1.strstr()函数--查找重复字符串第一次出现的位置
用于解决类似问题：给定两个字符串a,b，a字符串包含b字符串，求b字符串第一次在a字符串中出
现的位置，这时候我们就可以用strstr()函数了
include<bits/stdc++.h> using namespace std; int main() { char *str1 = "Hello"; char *str2 = "el"; char *result = strstr(str1,str2); cout<<result - str1<<endl; cout<<strstr(str1,str2)<<endl; }
strstr()函数中的数据类型是 char 和 char，这里就不得不提及char的三种定义字符串的方式了
char str[] = {'H','e','l','l','o','\0'}; cout<<str<<endl; char str1[] = "Hello"; cout<<str1<<endl; char *str2 = "Hello"; cout<<str2<<endl;
注意第一种写法最后的 '\0' 必须要写，否则输出时会产生乱码
2，KMP算法
使用next数组进行匹配的算法，一般先求next数组，再将母子数组进行比较
void getNext(int* next, const string& s) { int j = 0; next[0] = 0; for(int i = 1; i < s.size(); i++) { while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作 j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了 } if (s[i] == s[j]) { j++; } next[i] = j; } }
先求next数组
int strStr(string haystack, string needle) { if (needle.size() == 0) { return 0; } int next[needle.size()]; getNext(next, needle); int j = 0; for (int i = 0; i < haystack.size(); i++) { while(j > 0 && haystack[i] != needle[j]) { j = next[j - 1]; } if (haystack[i] == needle[j]) { j++; } if (j == needle.size() ) { return (i - needle.size() + 1); } } return -1; } };
结果与strstr()函数的结果一致
