PTA6-7 KMP算法

### PTA 平台上的 KMP 算法问题解析

#### 什么是KMP算法？

KMP算法的核心思想是在模式串与目标串不匹配的情况下，通过预先处理模式串来获取一个`next`数组。此数组记录了部分匹配的信息，使得当遇到失配情况时可以快速跳转到下一个可能的匹配位置而不必回溯目标串指针，从而提高效率[^1]。

#### 如何实现KMP算法中的Next数组构建?

为了计算给定模式串T的`next`数组，在PTA平台上通常会定义如下形式的方法：

void get_nextval(char T[], int next[]);

这里,T代表待求解的模式串,next则是用来存储对应于每一个字符的最大相等前后缀长度减一的结果集。具体来说就是对于任意i(0<i<T.length()),如果存在j满足条件S[0...j-1]=S[i-j...i-1],那么我们就说第i位之前的子串具有长度为j的最大相同前缀后缀;此时应设置next[i]=j-1。否则设next[i]=-1表示无这样的重复序列[^2]。

#### 实现完整的KMP搜索功能

同样地，在PTA上也会提供这样一个用于执行实际字符串匹配过程的功能接口:

int Index_KMP(char S[], char T[], int pos, int next[]);

其中参数说明:S为目标字符串；T为模板字符串；pos指示从哪个索引处开始尝试寻找第一个出现的位置；而最后一个参数next[]即为我们之前提到过的那个辅助性的跳跃表。返回值是一个整数型变量，它代表着所找到的第一个完全吻合项起始地址相对于整个源文本开头偏移量加1后的数值(-1意味着未发现任何符合条件的对象)。

下面给出一段基于上述两个函数完成简单版本KMP查找逻辑的C++示范代码片段：

#include <iostream>
using namespace std;

// 计算并填充next数组
void get_nextval(const string& pattern, vector<int>& next){
    int j = -1;
    next[0] = j;
    
    for(int i=1;i<pattern.size();){
        if(j==-1 || pattern[j]==pattern[i-1]){
            ++j;++i;
            if(pattern[j]!=pattern[i-1]) 
                next[i-1]=j;
            else 
                next[i-1]=next[j];
        }
        else{
            j=next[j];
        }   
    }
}

// 使用KMP算法进行字符串匹配
int index_kmp(const string& text,const string& pattern,vector<int> &next,int start_pos=0){
    int m=text.size(),n=pattern.size();
    int i=start_pos,j=0;
    
    while(i<m && j<n){
        if(j==-1||text[i]==pattern[j]){  
            i++;j++;
        }
        else{                            
            j=next[j];                   
        }
    }

    if(j>=n) return (i-n);
    else     return (-1);                
}

这段程序首先调用了`get_nextval()`方法初始化好了一个针对特定模式串优化好的转移规则列表——也就是所谓的“next”数组之后再借助后者实现了高效的线性时间复杂度内的精确检索操作 `index_kmp()`.