2023年7月20日发(作者：)

字符串的模式匹配算法——KMP模式匹配算法朴素的模式匹配算法(C++)朴素的模式匹配算法，暴⼒，容易理解#includeusing namespace std;int main(){ string mainStr, str; cin >> mainStr >> str; int i, j, pos = -1, count = 0; for(i = 0; i < (); i++) { for(j = 0; j < (); j++, i++) { if(mainStr[i] != str[j]) { break; } if(j == () - 1) { if(count == 0) { pos = i - j; //记录第⼀个与str相等的字符串在主串mainStr中的第⼀个字母的下标 } count++; //记录与str相等的字符串的数量 } } i = i - j; //对i值（主串指针）进⾏回溯操作 } cout << "pos=" << pos << ",count=" << count << endl; return 0;}KMP模式匹配算法(C++)KMP模式匹配算法相⽐较朴素的模式匹配算法，减少了主串指针回溯的操作#includeusing namespace std;int main(){ string mainStr, str; cin >> mainStr >> str; int i, j, pos = -1, count = 0; int next[256]; //计算next数组的数值 i = 0; j = -1; next[0] = -1; while(i < ()) { if(j == -1 || str[i] == str[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } //查找⼦串的位置和数量 i = 0; j = 0; while(i < ()) { if(mainStr[i] != str[j]) { j = next[j]; } else { if(j == () - 1) { if(count == 0) { pos = i - j; //记录⼦串第⼀次的第⼀个字母出现在主串中的位置 } count++; //记录在主串中含有⼦串的数量 } } i++; j++; } cout << "pos=" << pos << ",count=" << count << endl; return 0;}KMP模式匹配算法改进(C++)改进操作在于计算next数组数值的时候考虑了特殊情况 —— ⼦串形如abcabcabx#includeusing namespace std;int main(){ string mainStr, str; cin >> mainStr >> str; int i, j, pos = -1, count = 0; int next[256]; //计算next数组的数值 i = 0; j = -1; next[0] = -1; while(i < ()) { if(j == -1 || str[i] == str[j]) { i++; j++; if(str[j] == str[i]) { next[i] = next[j]; } else { next[i] = j; } } else { j = next[j]; } } //查找⼦串的位置和数量 i = 0; j = 0; while(i < ()) { if(mainStr[i] != str[j]) { j = next[j]; } else { if(j == () - 1) { if(count == 0) { pos = i - j; //记录⼦串第⼀次的第⼀个字母出现在主串中的位置 } count++; //记录在主串中含有⼦串的数量 } } i++; j++; } cout << "pos=" << pos << ",count=" << count << endl; return 0;}