2020-2021:teams:legal_string:各季度训练计划及训练记录:ac_自动机_lgwza
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:各季度训练计划及训练记录:ac_自动机_lgwza [2020/07/29 10:59] lgwza [KMP 自动机] |
2020-2021:teams:legal_string:各季度训练计划及训练记录:ac_自动机_lgwza [2020/07/29 11:17] (当前版本) lgwza [确定有限状态自动机] |
||
|---|---|---|---|
| 行 308: | 行 308: | ||
| - 状态转移函数 $\delta:Q\times\sum\rightarrow Q$，即 $\delta(q,\sigma)=q',q,q'\in Q,\sigma\in\sum$； | - 状态转移函数 $\delta:Q\times\sum\rightarrow Q$，即 $\delta(q,\sigma)=q',q,q'\in Q,\sigma\in\sum$； | ||
| - 一个开始状态 $s\in Q$； | - 一个开始状态 $s\in Q$； | ||
| - | - 一个接收的状态集合 $F\sube Q$。 | + | - 一个接收的状态集合 $F\subseteq Q$。 |
| 组成的五元组 $(Q,\sum,\delta,s,F)$。 | 组成的五元组 $(Q,\sum,\delta,s,F)$。 | ||
| 行 316: | 行 316: | ||
| ==== KMP 自动机 ==== | ==== KMP 自动机 ==== | ||
| - | KMP 自动机就是一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。如果共有 $m$ 个状态，第 $i$ 个状态表示已经匹配了前 $i$ 个字符。那么我们定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态，$next_i$ 表示 prefix function，则有：$$ | + | KMP 自动机就是一个不断读入待匹配串，每次匹配时走到接受状态的 DFA。如果共有 $m$ 个状态，第 $i$ 个状态表示已经匹配了前 $i$ 个字符。那么我们定义 $trans_{i,c}$ 表示状态 $i$ 读入字符 $c$ 后到达的状态，$next_i$ 表示 prefix function，则有： |
| - | trans_{i,c}=\begin{cases}i+1,&\text{if $b_{i}=c$} \\ [2ex]\text{trans}_{next_{i},c},&\text{else}\end{cases} | + | |
| - | $$（约定 $next_0=0$） | + | $$ |
| + | trans_{i,c}=\begin{cases}i+1,&\text{if $b_{i}=c$}\\[2ex]\text{trans}_{next_{i},c},&\text{else}\end{cases} | ||
| + | $$ | ||
| + | |||
| + | （约定 $next_0=0$） | ||
| 我们发现 $trans_i$ 只依赖于之前的值，所以可以跟 KMP 一起求出来。（一些细节：走到接受状态之后立即转移到该状态的 next） | 我们发现 $trans_i$ 只依赖于之前的值，所以可以跟 KMP 一起求出来。（一些细节：走到接受状态之后立即转移到该状态的 next） | ||
2020-2021/teams/legal_string/各季度训练计划及训练记录/ac_自动机_lgwza.1595991542.txt.gz · 最后更改: 2020/07/29 10:59 由 lgwza
