朴素模式匹配算法与KMP算法（非重点）

\quad

一. 朴素模式匹配算法

\quad

\quad

1.1 什么是字符串的匹配模式

\quad

\quad

\quad

1.2 朴素模式匹配算法

\quad

\quad

1.3 通过数组下标实现朴素模式匹配算法

\quad

鄙人所写

int Indexps(SString* a, SString* b) //朴素模式匹配算法
{int i = 1, j = 1;for (int k = 0; i < a->length - b->length + 1; k++){while(j<=b->length){if (a->ch[i] != b->ch[j]){break;}i++;j++;}if (j > b->length){return i - b->length;}i = i - j + 2;j = 1;if (i >= a->length - a->length + 2){return 0;}}
}

优化

\quad

二. KMP算法

\quad

\quad

2.1 算法分析

\quad

\quad
\quad
\quad
第二种情况




根据上面的经验，i不变，变的是j，而j是未知， 我们不妨先把j指向0

\quad

2.2 用代码实现（只会出现在选择题，考察代码的概率不大）

\quad
先不管next数组如何实现， 会手动算就行

\quad

三. 手算next数组

\quad

\quad
\quad

使用next数组进行模式匹配


练习题

\quad

四. KMP算法的进一步优化

\quad

\quad

4.1 优化分析

\quad

\quad
\quad
\quad
\quad


\quad
\quad
不是所有的next数组的值都可以被优化

\quad

\quad

4.2 手算nextval数组

\quad