前言——如何在不适用正则与 JavaScript Api 接口的条件下查找字符数按所在的位置？
winter 前端进阶训练营第六周
每一个状态都是一个机器
每一个机器知道下一个状态
v1.0
// 不用 api,不用正则,写一个 match
function match(string) {
for (let c of string) {
if (c === ‘a‘) {
return true;
}
}
return false;
}
match(‘I m groota‘);
v2.0
// 这里会有个问题, "a" 与 "b" 不相邻的时候也会判断为 true,怎么办呢???
function match(string) {
let foundA = false;
for (let c of string) {
if (c === ‘a‘) {
foundA = true;
} else if (foundA && c == ‘b‘) {
return true;
}
}
return false;
}
console.log(match(‘I acbm groot‘));
// 很简单
function match2(string) {
let foundA = false;
for (let c of string) {
if (c === ‘a‘) {
foundA = true;
} else if (foundA && c === ‘b‘) {
return true;
} else {
//////////////////////在这里多加一句话//////////////////////
foundA = false;
}
}
return false;
}
console.log(match2(‘I acbm groot‘));
v3.0
// 刚在写的是匹配 a,b 两个变量,那么如果要匹配三个变量呢?如果要匹配四个变量呢?在这里我们就使用到了有限状态机
// 首先我们定义五个状态,初始值为 false
// 然后在查找过程找,对状态进行变更
// 字符串中存在字符,便变更对应的状态为 true
// 倘若一旦有一个字符不匹配,重置所有的状态
function match(string) {
let foundA = false;
let foundB = false;
let foundC = false;
let foundD = false;
let foundE = false;
for (let c of string) {
if (c === ‘a‘) foundA = true;
else if (foundA && c === ‘b‘) foundB = true;
else if (foundB && c === ‘c‘) foundC = true;
else if (foundC && c === ‘d‘) foundD = true;
else if (foundD && c === ‘e‘) foundE = true;
else if (foundE && c === ‘f‘) return true;
else {
foundA = false;
foundB = false;
foundC = false;
foundD = false;
foundE = false;
}
}
return false;
}
console.log(match(‘I abm groot‘));
console.log(match(‘I abcdef‘));
v4.0
// 每个函数就是一个状态
// 函数参数就是输入
// 返回的是下一个状态
function state(input) {
return next;
}
function match(string) {
let state = start;
for (let c of string) {
console.log(c);
state = state(c);
}
return state === end;
}
function start(c) {
if (c === ‘a‘) return foundA;
else return start;
}
function end(c) {
return end;
}
function foundA(c) {
if (c === ‘b‘) return foundB;
else return start(c);
}
function foundB(c) {
if (c === ‘c‘) return end;
else return start(c);
}
function foundC(c) {
if (c === ‘d‘) return foundD;
else return start(c);
}
function foundD(c) {
if (c === ‘e‘) return foundE;
else return start(c);
}
function foundE(c) {
if (c === ‘f‘) return end;
else return start(c);
}
console.log(match(‘aacbc‘));
console.log(match(‘aacbcdefg‘));
v5.0
function match(string) {
let state = start;
for (let c of string) {
state = state(c);
}
return state === end;
}
function start(c) {
if (c === ‘a‘) return foundA;
else return start;
}
function end(c) {
return end;
}
function foundA(c) {
if (c === ‘b‘) return foundB;
else return start;
}
function foundB(c) {
if (c === ‘c‘) return foundC;
else return start;
}
function foundC(c) {
if (c === ‘a‘) return foundA2;
else return start;
}
function foundA2(c) {
if (c === ‘b‘) return foundB2;
else return start;
}
function foundB2(c) {
if (c === ‘x‘) return end;
else if (c === ‘c‘) return foundC;
else return start;
}
console.log(match(‘abcabcabx‘));
匹配“abababx”
可选： 撞击处理完全未知的pattern
参考： 字符串KMP算法
(这里先留个坑位了，算法刷完回来解决)
（参考链接）
原文：https://www.cnblogs.com/ssaylo/p/13139771.html