使用EGE图形库进行kmp算法演示

#include <graphics.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>

#define MAXSIZE 1000

void get_next(char *p, int *next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(p)) {
        if (j == -1 || p[i] == p[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

int kmp(char *s, char *p, int *next) {
    int i = 0, j = 0;
    while (i < strlen(s) && j < strlen(p)) {
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == strlen(p)) {
        return i - j;
    } else {
        return -1;
    }
}

int main() {
    char s[MAXSIZE], p[MAXSIZE];
    int next[MAXSIZE];
    initgraph(640, 480);
    setbkcolor(WHITE);
    cleardevice();
    settextcolor(BLACK);
    settextstyle(20, 0, "宋体");
    outtextxy(10, 10, "请输入主串：");
    outtextxy(10, 50, "请输入模式串：");
    settextstyle(16, 0, "宋体");
    rectangle(150, 5, 630, 35);
    rectangle(150, 45, 630, 75);
    while (kbhit()) getch();
    while (1) {
        if (kbhit()) {
            char c = getch();
            if (c == '\r') {
                break;
            } else if (c == '\b') {
                if (strlen(s) > 0) {
                    s[strlen(s) - 1] = '\0';
                    rectangle(150, 5, 630, 35);
                    outtextxy(150, 10, s);
                }
            } else {
                if (strlen(s) < MAXSIZE - 1) {
                    s[strlen(s)] = c;
                    s[strlen(s) + 1] = '\0';
                    rectangle(150, 5, 630, 35);
                    outtextxy(150, 10, s);
                }
            }
        }
    }
    while (kbhit()) getch();
    while (1) {
        if (kbhit()) {
            char c = getch();
            if (c == '\r') {
                break;
            } else if (c == '\b') {
                if (strlen(p) > 0) {
                    p[strlen(p) - 1] = '\0';
                    rectangle(150, 45, 630, 75);
                    outtextxy(150, 50, p);
                }
            } else {
                if (strlen(p) < MAXSIZE - 1) {
                    p[strlen(p)] = c;
                    p[strlen(p) + 1] = '\0';
                    rectangle(150, 45, 630, 75);
                    outtextxy(150, 50, p);
                }
            }
        }
    }
    get_next(p, next);
    int pos = kmp(s, p, next);
    if (pos != -1) {
        settextstyle(20, 0, "宋体");
        outtextxy(10, 100, "匹配成功！");
        settextstyle(16, 0, "宋体");
        char tmp[MAXSIZE];
        strncpy(tmp, s, pos);
        tmp[pos] = '\0';
        outtextxy(10, 150, tmp);
        settextcolor(RED);
        strncpy(tmp, s + pos, strlen(p));
        tmp[strlen(p)] = '\0';
        outtextxy(10 + pos * 10, 150, tmp);
        settextcolor(BLACK);
        strncpy(tmp, s + pos + strlen(p), strlen(s) - pos - strlen(p));
        tmp[strlen(s) - pos - strlen(p)] = '\0';
        outtextxy(10 + (pos + strlen(p)) * 10, 150, tmp);
    } else {
        settextstyle(20, 0, "宋体");
        outtextxy(10, 100, "匹配失败！");
    }
    while (!kbhit()) {
        Sleep(100);
    }
    closegraph();
    return 0;
}