KMPC++：深入解析与应用优化

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
using namespace std;
#define BUF_SIZE 256
int counts = 0;
int direction[200] = { 0 };
typedef struct seqstring {
char string[100];
int length;
}seqstring;
void getnext(seqstring p, int next[]) {
int i, j;
i = 0;//指向字符串每个字符的下标
j = -1;
next[i] = j;//next[0]放上-1
while (i if (j == -1 || p.string[i] == p.string[j]) {//如果是第一个字符或遇到相同的字符
next[++i] = ++j;
}
else {
j = next[j];
}
}
for (i = 0; i //printf("%d ", next[i]);
}
}
int kmp(seqstring t, seqstring p, int next[]) {
int i, j;
i = j = 0;
while (true) {
if (j == -1 || t.string[i] == p.string[j]) {
i++; j++;
}
else {
j = next[j];
}
if (!(i if (j == p.length) {
direction[counts] = i - p.length;
counts++;
j = 0;
}
if (i == t.length) {
return 0;
}
}
}
if (j == p.length)
{
return i - p.length;
}
else
{
return -1;
}
}
int main() {
seqstring t, p;
int next[50];
DWORD nIn;
char buffer[BUF_SIZE] = "";
HANDLE handle = CreateFile("test.txt",
GENERIC_READ,
FILE_SHARE_READ,
NULL,
OPEN_EXISTING,
FILE_ATTRIBUTE_NORMAL,
NULL);
if (handle == INVALID_HANDLE_VALUE) {
printf("%d", GetLastError());
return -1;
}
ReadFile(handle, buffer, BUF_SIZE, &nIn, NULL);
strcpy(t.string, buffer);
printf("%s\n", t.string);
t.length = strlen(t.string);
printf("please input string p:");
scanf("%s", p.string);
printf("%s\n", p.string);
p.length = strlen(p.string);
//printf("next:");
getnext(p, next);
kmp(t, p, next);
printf("\n%d\n", counts);
printf("单词出现的位置如下：\n");
for (int i = 0; i cout < }
}