串的模式匹配算法
一,基本模式匹配算法
#include<iostream> #include <cstring> using namespace std; int main() { char str1[] = "abchelloefg"; char str2[] = "hello"; int i = 0, j = 0, flag = 0, len1 = strlen(str1), len2 = strlen(str2); for (i = 0; i < len1; i++){ if (str1[i] == str2[j]){ while (str1[i + j] == str2[j] && i + j < len1 && j < len2){ j++; } if (j == len2){ flag = 1; break; }else if (i + j == len1){ flag = 0; break; }else{ j = 0; } } } if (flag == 0){ cout<<"无匹配字符串"<<endl; }else if (flag == 1){ cout<<str1+i<<endl; } return 0; }
二,模式匹配的改进算法----KMP算法
此算法的改进在于:每当一趟匹配过程中出现字符不等时,不需要回溯i指针,而是利用已经得到“部分匹配”的结果模式向右滑动尽可能远的一段距离后,继续进行比较。
此算法需要求解next[]数组,此数组存放子字符串的一些值,将两个字符串比较原理用于一个字符串两部分比较。
具体算法实现:
#include <iostream> using namespace std; const int N = 100; void setNext(char *str, int len, int *next) { next[0] = -1; int i = 0, j = -1; while (i < len - 1) { if (j == -1 || str[i] == str[j]){ i++; j++; next[i] = j; }else{ j = next[j]; } } } int main() { char str1[] = "abchelloefg", str2[] = "hello"; int next[N], len1 = strlen(str1), len2 = strlen(str2); setNext(str2, len2, next); int i = 0, j = 0; while (i < len1 && j < len2){ if (j == -1 || str1[i] == str2[j]){ i++; j++; }else{ j = next[j]; } } if (j == len2){ cout<<str1+i-len2<<endl; }else{ cout<<"没有匹配的字符串"<<endl; } return 0; }