数据结构C语言代码在聊天信息中查找是否有转账字符串，要求利用串的KMP模式匹配算法实现查找子串。用kmp算法

在C语言中，要使用KMP（Knuth-Morris-Pratt）算法来查找聊天信息中的转账字符串，首先需要了解KMP算法的基本原理。这个算法用于在文本串中查找指定模式串，通过构建部分匹配表（也叫失配函数）避免了无效的比较，提高了搜索效率。

以下是一个简单的C语言实现步骤：

1. **部分匹配表构建**：
- 定义一个数组`lps[]`存储模式串的失配信息。
- 初始化`lps[0] = 0`表示前缀和空串有相同的长度。
- 从第二个字符开始，对于每个位置`i`：
- 如果`pattern[i] == pattern[j]`（`j`是上一次成功的匹配位置），则`lps[i] = j + 1`。
- 否则，如果`j != 0`，则尝试缩小范围到`lps[j - 1]`，即查找是否存在`pattern[j]`之前的相同部分，直到找到或`j = 0`。

2. **实际查找**：
- 对于聊天信息`text`和模式串`pattern`：
- 遍历`text`，从头开始，当前指针设为`i = 0`。
- 比较`text[i]`和`pattern[j]`：
- 如果相等，递增`i`和`j`。
- 如果不相等，检查`j`是否为0，如果不是，则跳转到`lps[j - 1]`继续；如果是，则说明未找到匹配，`i++`继续比较下一个字符。

3. **返回结果**：
- 当`j == length(pattern)`时，找到了一个匹配，并记录起始位置。
- 如果遍历完`text`还没找到匹配，返回-1或相应的标志表示没有找到。

以下是部分代码片段示例：

#include <stdio.h>
#include <string.h>

// KMP表构造函数
void compute_lps(char *pattern, int lps[], int len) {
    int i = 1;
    while (i < len) {
        if (pattern[i] == pattern[lps[i - 1]]) {
            lps[i] = lps[i - 1] + 1;
            i++;
        } else {
            if (lps[i - 1] != 0)
                i = lps[i - 1];
            else
                lps[i] = 0;
        }
    }
}

// KMP搜索函数
int kmp_search(char *text, char *pattern, int text_len, int pattern_len) {
    int i = 0, j = 0, lps[pattern_len];
    compute_lps(pattern, lps, pattern_len);
    
    while (i < text_len) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        if (j == pattern_len) {
            // 找到了匹配
            return i - pattern_len;
        } else if (i < text_len && text[i] != pattern[j]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }

    // 没有找到匹配
    return -1;
}

// 主函数演示
int main() {
    char chat_info[] = "对方转账50元";
    char transfer[] = "转账";
    int text_len = strlen(chat_info);
    int pattern_len = strlen(transfer);
    int match_pos = kmp_search(chat_info, transfer, text_len, pattern_len);

    if (match_pos != -1)
        printf("转账字符串在聊天信息中的位置: %d\n", match_pos);
    else
        printf("找不到转账字符串\n");

    return 0;
}