void KmpGenNext(char* p, int* next) //生成p的next数组, next数组长度大于等于字符串p的长度加1 { // 请在此添加代码,补全函数KmpGenNext /********** Begin *********/
时间: 2024-05-15 22:11:34 浏览: 7
KMP算法是一种高效的字符串匹配算法,其中生成next数组是KMP算法的重要部分。下面是void KmpGenNext(char* p, int* next)函数的实现代码:
void KmpGenNext(char* p, int* next)
{
int i = 0, j = -1;
int len = strlen(p);
next = -1;
while (i < len) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
在这段代码中,我们使用了两个变量i和j,i指向当前字符,j指向上一个匹配的字符。next数组表示模式串p中前缀和后缀的最长公共部分的长度。我们初始化next为-1,i从0开始,j初始化为-1。接着,我们使用一个while循环来遍历整个字符串p。当p[i]等于p[j]时,说明当前字符匹配成功,将next[i+1]赋值为j+1即可。如果不匹配,则需要将j更新为next[j],直到j等于-1或者p[i]等于p[j]为止。
相关问题
void getNext(char* p, int* next)
这个函数是一个实现 KMP 字符串匹配算法中“求解 next 数组”的函数。其中,参数 p 是要匹配的模式串,next 数组记录了模式串每一位匹配失败时跳转的位置。
具体来说,算法从模式串的第一位开始,维护两个指针 i 和 j,表示当前匹配的位置和已知的部分匹配位置。如果当前位置和已知位置匹配,则两个指针同时向右移动一位,并将 next[i+1] 赋值为 j+1。如果不匹配,则将已知位置 j 向左跳转到 next[j] 所记录的位置,再次进行匹配。
最终,当 i 超过模式串的长度时,next 数组就求解完成了。
使用链表,用户输入n,再输入n个长度不超过20的有序字符串(按照字典顺序),再输入一个字符串(长度不超过20),将其插入现有字符串数组后仍有序。 函数原型:void (char (*p)[21],int n, char *t);
好的,这个问题可以使用链表来解决。具体实现可以参考下面的代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
// 定义链表节点
struct Node {
char str[21];
Node *next;
};
void insertString(Node *&head, char *t) {
// 创建新节点
Node *newNode = new Node();
strcpy(newNode->str, t);
newNode->next = NULL;
// 找到插入位置
Node *pre = NULL, *cur = head;
while (cur != NULL && strcmp(cur->str, t) < 0) {
pre = cur;
cur = cur->next;
}
// 将新节点插入链表
if (pre == NULL) {
newNode->next = head;
head = newNode;
} else {
newNode->next = pre->next;
pre->next = newNode;
}
}
void printList(Node *head) {
while (head != NULL) {
cout << head->str << " ";
head = head->next;
}
cout << endl;
}
int main() {
int n;
cin >> n;
// 创建链表
Node *head = NULL;
for (int i = 0; i < n; i++) {
char str[21];
cin >> str;
insertString(head, str);
}
// 插入新字符串
char str[21];
cin >> str;
insertString(head, str);
// 输出链表
printList(head);
return 0;
}
```
这个程序首先读入输入的字符串,然后根据输入的字符串创建一个链表。接着,读入要插入的字符串,将其插入到链表中。最后,输出链表即可。
需要注意的是,这个程序使用了一个链表来存储输入的字符串,其中每个节点包含一个字符串和一个指向下一个节点的指针。在插入新字符串时,需要遍历链表找到插入位置,然后将新节点插入到对应位置即可。
相关推荐
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)