实现基于链表结构的字符串匹配算法

链表结构的字符串匹配算法可以采用单向链表（每个节点含有一个字符）或双向链表（每个节点含有一个字符和前驱指针、后继指针）实现。其中，单向链表实现相对简单，以下以单向链表为例进行实现。

基本思路：

1. 从主串的第一个字符开始，依次匹配模式串的每个字符。

2. 如果主串当前字符与模式串当前字符相等，则继续匹配下一个字符。

3. 如果当前字符不相等，则从主串下一个字符开始重新匹配。

4. 如果匹配成功，返回匹配的起始位置；否则返回-1。

具体实现：

1. 定义一个链表结构体，包含字符数据和指向下一个节点的指针。

2. 定义一个函数，接收主串和模式串作为参数，返回匹配的起始位置。

3. 在函数中，将主串和模式串分别转换为链表结构，即创建主串链表和模式串链表。

4. 从主串链表的第一个节点开始遍历，对于每个节点，从模式串链表的第一个节点开始遍历，对于每个节点，如果字符相等，则继续比较下一个节点，否则返回主串链表中下一个节点，并重新从模式串链表的第一个节点开始比较。

5. 如果模式串链表遍历完毕，则匹配成功，返回当前主串链表节点的位置；否则返回-1。

以下是单向链表实现的代码示例：

#include <iostream>
#include <cstring>

using namespace std;

// 链表结构体
struct Node {
    char data;
    Node* next;
};

// 创建链表
Node* createList(const char* str) {
    if (!str) {
        return NULL;
    }
    Node* head = new Node();
    head->next = NULL;
    Node* cur = head;
    for (int i = 0; i < strlen(str); i++) {
        Node* newNode = new Node();
        newNode->data = str[i];
        newNode->next = NULL;
        cur->next = newNode;
        cur = cur->next;
    }
    return head;
}

// 字符串匹配
int stringMatch(Node* mainList, Node* patternList) {
    if (!mainList || !patternList) {
        return -1;
    }
    Node* mainCur = mainList->next;
    while (mainCur) {
        Node* patternCur = patternList->next;
        Node* matchCur = mainCur;
        while (patternCur) {
            if (!matchCur) {
                break;
            }
            if (matchCur->data == patternCur->data) {
                matchCur = matchCur->next;
                patternCur = patternCur->next;
            } else {
                break;
            }
        }
        if (!patternCur) {
            return mainCur - mainList;
        }
        mainCur = mainCur->next;
    }
    return -1;
}

int main() {
    const char* mainStr = "hello, world!";
    const char* patternStr = "world";
    Node* mainList = createList(mainStr);
    Node* patternList = createList(patternStr);
    int pos = stringMatch(mainList, patternList);
    if (pos >= 0) {
        cout << "Matched, position: " << pos << endl;
    } else {
        cout << "Not matched" << endl;
    }
    return 0;
}