#include <stdio.h> #include <stdlib.h> #include <string.h> struct String { char *data; int length; }; void initString(struct String *S) { S->data = NULL; S->length = 0; } void assignString(struct String *S, char *str) { int len = strlen(str); if (len == 0) { if (S->data != NULL) { free(S->data); S->data = NULL; S->length = 0; } } else { if (S->data != NULL) { free(S->data); } S->data = (char *)malloc(sizeof(char) * (len + 1)); strcpy(S->data, str); S->length = len; } } void printString(struct String *S) { if (S->data == NULL) { printf("Empty String\n"); } else { printf("%s\n", S->data); } } void getNext(struct String *P, int *next) { int i = 0, j = -1; next[0] = -1; while (i < P->length) { if (j == -1 || P->data[i] == P->data[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } } int KMP(struct String *T, struct String *P) { int i = 0, j = 0; int *next = (int *)malloc(sizeof(int) * (P->length + 1)); getNext(P, next); while (i < T->length && j < P->length) { if (j == -1 || T->data[i] == P->data[j]) { i++; j++; } else { j = next[j]; } } free(next); if (j == P->length) { return i - j; } else { return -1; } } int main() { struct String T, P; initString(&T); initString(&P); assignString(&T,"ababcabcacbab"); assignString(&P,"abcac"); printf("T: "); printString(&T); printf("P: "); printString(&P); int pos = KMP(&T, &P); if (pos != -1) { printf("模式串在主串中的位置是:%d", pos); } else { printf("未找到模式串!\n"); } return 0; }将以上程序修改为在运行中输入T和P
时间: 2023-12-14 11:38:58 浏览: 24
以下是修改后的代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct String {
char *data;
int length;
};
void initString(struct String *S) {
S->data = NULL;
S->length = 0;
}
void assignString(struct String *S, char *str) {
int len = strlen(str);
if (len == 0)
{
if (S->data != NULL)
{
free(S->data);
S->data = NULL;
S->length = 0;
}
}
else
{
if (S->data != NULL)
{
free(S->data);
}
S->data = (char *)malloc(sizeof(char) * (len + 1));
strcpy(S->data, str);
S->length = len;
}
}
void printString(struct String *S) {
if (S->data == NULL)
{
printf("Empty String\n");
}
else
{
printf("%s\n", S->data);
}
}
void getNext(struct String *P, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (i < P->length)
{
if (j == -1 || P->data[i] == P->data[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
int KMP(struct String *T, struct String *P) {
int i = 0, j = 0;
int *next = (int *)malloc(sizeof(int) * (P->length + 1));
getNext(P, next);
while (i < T->length && j < P->length)
{
if (j == -1 || T->data[i] == P->data[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
free(next);
if (j == P->length)
{
return i - j;
}
else
{
return -1;
}
}
int main() {
struct String T, P;
initString(&T);
initString(&P);
char t[100], p[100];
printf("请输入主串T:");
scanf("%s", t);
printf("请输入模式串P:");
scanf("%s", p);
assignString(&T, t);
assignString(&P, p);
printf("T: ");
printString(&T);
printf("P: ");
printString(&P);
int pos = KMP(&T, &P);
if (pos != -1)
{
printf("模式串在主串中的位置是:%d", pos);
}
else
{
printf("未找到模式串!\n");
}
return 0;
}
```