动态规划-KMP字符匹配算法

动态规划之KMP字符匹配算法
把KMP看成输入不只有0/1的Moore型（数字逻辑）（直接ASCII：266或是大小写：52） **
看成动归：状态，和选择
构建状态转移图
分成状态推进，与重启
要去的状态：
影子状态（我编的名字），用变量 X 表示。所谓影子状态，就是和当前状态具有相同的前缀。（应该是要对他遍历）
KMP 就是要尽可能少的回退**，以免多余的计算：j 就可以去问问和自己具有相同前缀的 X，如果 X 遇见 “A” 可以进行「状态推进」，那就转移过去
那就是从大数往开头遍历，遇到可以推进的：
如果遇到的字符是 “B”，状态 X 也不能进行「状态推进」，只能回退
因为 X 永远跟在 j 的身后，状态 X 如何转移，在之前就已经算出来了（动态规划思想：利用过去的结果解决现在的问题）
c++如何取出string中的第一个字符…
没没看懂：
X是pat自己匹配自己
核心在于：
1.j游标下，只有获得pat 【j】才会加一，其他都可以由状态X决定
2.X游标下，X一定落后于j，直接用j做好的数组，就可以决定X的状态转换，因为j从1开始，X从0开始，越拉越远

 for (int j = 1; j < M; j++) {for (int c = 0; c < 256; c++)dp[j][c] = dp[X][c];dp[j][pat.charAt(j)] = j + 1;//核心// 更新影子状态X = dp[X][pat.charAt(j)];//核心

而其中X = dp[X][pat.charAt(j)];就相当于，当前X获得了j的输入，会怎么样，

public class KMP {private int[][] dp;private String pat;public KMP(String pat) {this.pat = pat;int M = pat.length();// dp[状态][字符] = 下个状态dp = new int[M][256];// base casedp[0][pat.charAt(0)] = 1;//只有遇到 pat[0] 这个字符才能使状态从 0 转移到 1，其他都是0状态// 影子状态 X 初始为 0///就是最开始你们只要错了就都回最开始int X = 0;// 当前状态 j 从 1 开始for (int j = 1; j < M; j++) {for (int c = 0; c < 256; c++) {if (pat.charAt(j) == c) dp[j][c] = j + 1;//意思是下一个状态else dp[j][c] = dp[X][c];//意思是状态退回到影子状态时获得C的情况（且，dpX，C （如X状态下获得C不加一的话）还与dpX-1，C相同 ）}// 更新影子状态X = dp[X][pat.charAt(j)];///j进了1，相应的X，就是原来的X 时，获得了j所应有的状态}}public int search(String txt) {...}
}

看完上面：看summary的会更扎实
动图找gif分解看吧
翻墙就行

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！