1.根据字符构造trie树 2.构建失败匹配指针 1.根节点的所以一代子孩子失败指针都指向root 2.子节点匹配失败时，找到父节点的失败指针，找不到就一直找，直到找到root还匹配不到，直接指向root 3.文本串匹配 1.如果已经匹配到完整的模式串或者压根匹配不到，根据失败指针切换线路继续向下查找 2.如果匹配到了，那么就继续向下匹配
我要评论class acnode {
constructor(data){
this.data = data
this.isendingchar = false
this.children = new map()
this.length = 0
this.fail = null
}
}
class actree {
constructor(){
this.root = new acnode('/')
}
insert(text){
let node = this.root
for(let char of text ){
if(!node.children.get(char)){
node.children.set(char,new acnode(char))
}
node = node.children.get(char)
}
node.isendingchar = true
node.length = text.length
}
failurepointer(){
let root = this.root
let queue = []
queue.push(root)
while(queue.length > 0){
let currentnode = queue.shift()
for(let child of currentnode.children.values()){
if(!child){
continue
}
if(currentnode == root){
child.fail = currentnode
}else{
//不是一代子节点才指向
let grandfathernode = currentnode.fail
while(grandfathernode){
let failnode = grandfathernode.children.get(child.data)
if(failnode){
child.fail = failnode
//找到失败节点就不往下找了
break
}
grandfathernode = grandfathernode.fail
}
if(!grandfathernode){
child.fail = root
}
}
queue.push(child)
}
}
}
match(text){
let root = this.root
let len = text.length
let currentnode
for(let i = 0; i < len; i++){
let char = text[i]
if(!currentnode){
currentnode = root
}
while(!currentnode.children.get(char) && currentnode != root){
//匹配不到就换线
currentnode = currentnode.fail
}
currentnode = currentnode.children.get(char)
let tmp = currentnode
while(tmp != root){
if(tmp.isendingchar){
console.log(`from ${i - tmp.length + 1} length: ${tmp.length} str: ${text.substr(i - tmp.length + 1,tmp.length)}`)
}
//匹配到了就继续看看其他线有没有可以匹配成功的
tmp = tmp.fail
}
}
}
}
function match(text,patterns){
const autometa = new actree()
for(pattern of patterns){
autometa.insert(pattern)
}
autometa.failurepointer()
autometa.match(text)
}
let patterns = ["at", "art", "oars", "soar"];
let text = "soarsoars";
match(text, patterns);
let patterns2 = ["fxtec pro1", "谷歌pixel"];
let text2 = "一家总部位于伦敦的公司fxtex在mwc上就推出了一款名为fxtec pro1的手机，该机最大的亮点就是采用了侧滑式全键盘设计。dxomark年度总榜发布 华为p20 pro/谷歌pixel 3争冠";
match(text2, patterns2);
如对本文有疑问， 点击进行留言回复！！
Android 入门第六讲05-JSON解析第三方框架Gson（GSON框架使用方法，GSON解析Json数据（json对象，对象嵌套，数组，对象数组，json对象嵌套JSON对象数组））
网友评论