KMP算法
KMP算法 是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法。
重点是找到字符串的最长公共前后缀。用最长公共前后缀在匹配的同时,实现快速跳转。
KMP的时间复杂度
假设 m为模式串strM的长度,n为待匹配的字符串strN的长度。
时间复杂度为 (O(m+n))
参考文档:
KMP时间复杂度分析
#include
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int Maxn = 1e6 + 5;
int la, lb;
int nxt[Maxn];
char a[Maxn], b[Maxn];
inline void kmp() { //字符串: 1 ~ lb;
nxt[1] = 0;
for (int i = 2, j = 0; i
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net