1、字符串匹配问题 给定一个s字符串和一个n字符串,在s字符串中找出n字符串出现的第一个位置(从0开始)。如果不存在,则返回 -1(需要给出多个测试用例,证明算法的正确性)。
时间: 2024-02-22 15:54:39 浏览: 25
好的,这是一个常见的字符串匹配问题,可以使用KMP算法或者Rabin-Karp算法来解决。下面给出一个KMP算法的实现示例,并给出一些测试用例验证算法的正确性。
KMP算法的主要思想是利用已匹配的前缀信息来避免不必要的比较。具体实现可以使用一个next数组来记录模式串中不匹配时需要跳过的位置。
以下是KMP算法的实现示例(使用C++语言):
```
#include <iostream>
#include <vector>
using namespace std;
vector<int> getNext(const string& pattern) {
int n = pattern.length();
vector<int> next(n, -1);
int i = 0, j = -1;
while (i < n - 1) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
return next;
}
int kmp(const string& text, const string& pattern) {
int m = text.length();
int n = pattern.length();
if (n == 0) return 0;
vector<int> next = getNext(pattern);
int i = 0, j = 0;
while (i < m && j < n) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == n) {
return i - n;
} else {
return -1;
}
}
int main() {
string s1 = "hello world";
string n1 = "world";
cout << kmp(s1, n1) << endl; // expect 6
string s2 = "hello world";
string n2 = "worl";
cout << kmp(s2, n2) << endl; // expect -1
string s3 = "hello world";
string n3 = "";
cout << kmp(s3, n3) << endl; // expect 0
string s4 = "aaa";
string n4 = "a";
cout << kmp(s4, n4) << endl; // expect 0
string s5 = "aaa";
string n5 = "b";
cout << kmp(s5, n5) << endl; // expect -1
return 0;
}
```
上面的测试用例覆盖了一些边界情况,可以验证算法的正确性。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)