KMP理解: 假定在匹配中,正在比较的文本串位置和模板串abbaaba最后一个字符不符合(失配),这是朴素算法会将模板串右移一位,继续比较,但是kmp不这样做,kmp认为既然!!位置已经比较过,应该可以利用模板串本身属性判断出右移一位不能匹配,同理,右移两位或者三位也不行,但是右移四位是有可能的。这个时候,需要比较 ‘’‘’*处的字符和abbaaba的第三个字符。 下面那个链状图就是一个状态机,其中编号为i的节点表示已经匹配了i个字符,匹配开始是0,如果成功匹配则+1,失配时‘沿着失配边走’,如果在状态6处失配,应…

2017年7月23日 0条评论 10点热度 阅读全文