北邮22信通一枚~   

跟随课程进度每周更新数据结构与算法的代码和文章 

持续关注作者  解锁更多邮苑信通专属代码~

上一篇文章：

下一篇文章：

*说明*

1.本代码结合书上第二章线性表和4.3.3KMP算法结合书写。

2.加快匹配速度的根本原因：前缀子串无需匹配。

3.关于申请堆区动态数组的缓冲区问题：

        每次申请堆空间时，系统会自动利用已经申请单还未利用的堆空间作为数据缓冲区，通俗的讲，就是系统要给你将要输入的数据提前预测一下区域，看看你再输入数据之后会不会导致数据溢出。

        程序很害怕这种事情发生，所以总是很小心翼翼的留出一个数据缓冲区，每次你输入完数据，数据都会进入上一次输入数据时产生的缓冲区中，然后缓冲区后移；直到缓冲区到了申请的堆空间最低端，程序就会发出警告，如果你再不考虑多申请一点堆空间的话，数据就要溢出啦！！！然后就会在语句底下给你画小绿线……所以！！！适当多申请点儿空间！！！

4.KMP函数中的实现过程和BF算法类似，明白了BF自然就轻轻松松明白KMP，所以重点是前面写的getnextarray函数。

*说明完毕*

一.顺序表实现KMP算法

KMP算法部分：

template<class temp>
void seqlist<temp>::getnextarray(seqlist<temp>& t, int*& next)
{next = new int[t.getlength() + 10];/*如果写成next = new int[t.getlength() + 1]会有建议提示：“写入next时缓存区溢出”，原因如下：next动态数组缓冲区溢出动态数组基本全部被占满，数据缓冲区不够；所以应多给动态数组分配一点存储空间以增加缓存区容量*/next[1] = 0;next[2] = 1;int p = 1;for (int j = 3; j <= t.getlength(); ++j){while (p > 1 && t.get(p) != t.get(j - 1))p = next[p];if (t.get(p) == t.get(j - 1))++p;next[j] = p;}
}template<class temp>
int seqlist<temp>::KMP(seqlist<temp>& t)
{int* next;getnextarray(t, next);int i = 1, j = 1;while (i <= this->getlength() && j <= t.getlength()){if (get(i) == t.get(j)){i++; j++;}else if (!next[j]){i++; j = 1;}elsej = next[j];}delete[]next;if (j > t.getlength())return i + 1 - j;else return -1;
}

代码部分及运行结果：

#include <iostream>
using namespace std;
#define N 100
template<class temp>
class seqlist
{
private:temp data[N];int length;
public:seqlist() { length = 0; }seqlist(temp a[], int n);int getlength() { return length; }void printlist();void insert(int i, temp x);temp del(int i);temp get(int i);int locate(temp x);void getnextarray(seqlist<temp>& t, int*& next);int KMP(seqlist<temp>& t);
};template <class temp>
seqlist<temp>::seqlist(temp a[], int n)
{if (n > N)throw "数组长度超过顺序表最大长度";for (int i = 0; i < n; i++)this->data[i] = a[i];this->length = n;
}template<class temp>
void seqlist<temp>::printlist()
{cout << "按序号依次遍历线性表中各个数据元素:" << endl;for (int i = 0; i < this->length; i++)this->data[i].print();cout << endl;
}template<class temp>
void seqlist<temp>::insert(int i, temp x)
{if (this->length >= N)throw"上溢异常";if (i < 1 || i >= this->length + 1)throw"位置异常";for (int j = this->length; j >= i; j--)this->data[j] = this->data[j - 1];this->data[i - 1] = x;this->length++;
}template<class temp>
temp seqlist<temp>::del(int i)
{if (this->length == 0)throw"下溢异常";if (i<1 || i>this->length)throw"位置异常";temp x = data[i - 1];for (int j = i; j < this->length; j++)data[j - 1] = data[j];this->length--;return x;
}template<class temp>
temp seqlist<temp>::get(int i)
{if (i<1 || i>this->length)throw"查找位置非法";return this->data[i - 1];
}template<class temp>
int seqlist<temp>::locate(temp x)
{for (int i = 0; i < this->length; i++)if (this->data[i] == x)return(i + 1);return 0;
}template<class temp>
void seqlist<temp>::getnextarray(seqlist<temp>& t, int*& next)
{next = new int[t.getlength() + 10];/*如果写成next = new int[t.getlength() + 1]会有建议提示：“写入next时缓存区溢出”，原因如下：next动态数组缓冲区溢出动态数组基本全部被占满，数据缓冲区不够；所以应多给动态数组分配一点存储空间以增加缓存区容量*/next[1] = 0;next[2] = 1;int p = 1;for (int j = 3; j <= t.getlength(); ++j){while (p > 1 && t.get(p) != t.get(j - 1))p = next[p];if (t.get(p) == t.get(j - 1))++p;next[j] = p;}
}template<class temp>
int seqlist<temp>::KMP(seqlist<temp>& t)
{int* next;getnextarray(t, next);int i = 1, j = 1;while (i <= this->getlength() && j <= t.getlength()){if (get(i) == t.get(j)){i++; j++;}else if (!next[j]){i++; j = 1;}elsej = next[j];}delete[]next;if (j > t.getlength())return i + 1 - j;else return -1;
}int main()
{system("color 0A");char a[] = "hello world";char b[] = "good";char c[] = "ello";seqlist<char>seqa(a, strlen(a));seqlist<char>seqb(b, strlen(b));seqlist<char>seqc(c, strlen(c));cout << seqa.KMP(seqa) << endl;//1cout << seqa.KMP(seqb) << endl;//-1cout << seqa.KMP(seqc) << endl;//2return 0;
} 

“诶博主 你是不是少了一个主标题和内容啊”

“没有没有没有！”（理直气壮）（逃跑）

等我醒了再更……