class Solution { public: int strStr(string haystack, string needle) { int n = haystack.size(), m = needle.size(); if (m == 0) { return 0; } vector<int> pi(m); for (int i = 1, j = 0; i < m; i++) { while (j > 0 && needle[i] != needle[j]) { j = pi[j - 1]; } if (needle[i] == needle[j]) { j++; } pi[i] = j; } for (int i = 0, j = 0; i < n; i++) { while (j > 0 && haystack[i] != needle[j]) { j = pi[j - 1]; } if (haystack[i] == needle[j]) { j++; } if (j == m) { return i - m + 1; } } return -1; } };这个算法的核心逻辑是什么
时间: 2024-02-14 10:12:37 浏览: 19
这个算法使用了KMP算法的思想,在匹配过程中,利用前缀表(pi数组)记录模式串中每个前缀的最长公共前后缀长度,并根据前缀表中的信息调整模式串的匹配位置。具体来说,对于文本串中的每个字符,如果与模式串中的当前字符不匹配,就根据前缀表中记录的信息将模式串向右移动一定的距离(即pi[j-1]),直到匹配或模式串移动到末尾为止。如果匹配成功,就返回匹配的起始位置。如果匹配失败,则继续在文本串中匹配下一个字符,直到文本串遍历完为止。
相关问题
<string.h>函数中的strstr的实现
strstr函数用于在一个字符串中查找一个子字符串,并返回第一次出现该子字符串的地址。其实现大致如下:
```c
char *strstr(const char *haystack, const char *needle) {
size_t needle_len = strlen(needle);
if (needle_len == 0) {
return (char *)haystack;
}
while (*haystack) {
if (strncmp(haystack, needle, needle_len) == 0) {
return (char *)haystack;
}
++haystack;
}
return NULL;
}
```
以上实现中,首先计算出needle的长度,如果长度为0则直接返回haystack的地址。接下来在while循环中,每次比较haystack和needle的前needle_len个字符,如果相等则返回haystack的地址。如果循环结束还没有找到needle,则返回NULL。
需要注意的是,由于该函数返回的是指向haystack中某个位置的指针,因此需要将返回值强制转换为char *类型。
用c++举例string.fing函数用法
字符串函数 `strstr()` 可以在一个字符串中查找另一个字符串的出现位置。它的函数原型如下:
```c
char *strstr(const char *haystack, const char *needle);
```
其中,`haystack` 是要搜索的字符串,`needle` 是要查找的子字符串。函数返回值是一个指向 `haystack` 中第一次出现 `needle` 的位置的指针,如果没有找到,则返回 `NULL`。
举个例子,假设我们要在字符串 `haystack` 中查找字符串 `needle` 的出现位置,可以这样写:
```c
#include <stdio.h>
#include <string.h>
int main() {
char haystack[] = "hello, world";
char needle[] = "world";
char *result = strstr(haystack, needle);
if (result == NULL) {
printf("'%s' not found in '%s'\n", needle, haystack);
} else {
printf("'%s' found at position %ld in '%s'\n", needle, result - haystack, haystack);
}
return 0;
}
```
输出结果为:
```
'world' found at position 7 in 'hello, world'
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)