# StringMatch_KMP

**Repository Path**: vaster4/string-match-kmp

## Basic Information

- **Project Name**: StringMatch_KMP
- **Description**: 模式匹配，KMP算法
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2023-04-18
- **Last Updated**: 2023-04-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# StringMatch_KMP

[gitee仓库：](https://gitee.com/vaster4/string-match-kmp.git)

堆结构储存设计的串设计如下：

```c++
#ifndef STRING_H
#define STRING_H
typedef bool Status;
const Status OK = true;
const Status ERROR = false;

/**
 * 堆储存字符串
 * 储存结构中，串的有效元素从数组的第零个开始，这与教材的定义有一定的区别
 * 实现了KMP算法
 * @author LuoHao
 *
 */
class String {
    int _length;
    char *ch;

public:
    // 获取内容
    [[nodiscard]] const char *toChars() const;

    operator const char *();

public:
    // 构造器
    String();

    String(const char *chars);

    String(const String &S);

    // 析构器
    ~String();

public:
    // 最小操作集
    Status assign(const char *chars);

    int length(void) const;

    int compareTo(const String &T) const;

    Status clear(void);

    String &concat(const String &S1, const String &S2);

    String substring(int pos, int len) const;

public:
    // 附加操作集
    String &append(const String &S2);//拼接自己和另一个字符串
    String replace(const String &T, const String &V);

    int index_KMP(const String &T, int pos = 0) const;

private:
    void getNextForKMP(int next[]) const;
};

#endif // !STRING_H

```

其中replace和KMP算法的实现如下：

```c++

void sampleReplace() {
    cout << "sample replace:" << endl;
    char str[] = "a.cpp, b.cpp c.cpp d.cpp cpp.cpp";
    cout <<"before: "<< str << endl;
    String a(str);
    cout <<R"(replace "cpp" with "py": )"<< a.replace("cpp", "py") << endl << endl;
}


int String::index_KMP(const String &T, int pos) const {
    int *next = new int[T.length()];
    T.getNextForKMP(next);
    int i = pos;
    int j = 0;
    while (i < _length && j < T.length()) {
        if (j == -1 || ch[i] == T.ch[j]) {
            ++i;
            ++j;
        } else
            j = next[j];
    }
    delete next;
    if (j < T.length())
        return -1;
    return i - T.length();
}

void String::getNextForKMP(int next[]) const {
    int i = 0;
    next[0] = -1;
    int j = -1;
    while (i < _length - 1) {
        if (j == -1 || ch[i] == ch[j]) {
            ++i;
            ++j;
            next[i] = j;
        } else
            j = next[j];
    }
}
```

最后的运行结果如下：

![](screenshots/result.png)