// 計算next數(shù)組
function calcNext(str) {
let next = [-1],
len = str.length,
i = 1,
j = -1;
for (i = 1; i < len; i++) {
while (str[i] !== str[j + 1] && j > -1) {
j = next[j];
}
if (str[j + 1] === str[i]) {
j = j + 1;
}
next[i] = j;
}
return next;
}
// source 源字符串
// match 要匹配的字符串
// res 保存匹配位置的數(shù)組
function search(source, match) {
let next = calcNext(match),
m = source.length,
n = match.length,
i = 0,
j = 0,
res = [];
while (i < m - n) {
if (source[i] === match[j]) {
i++;
j++;
if (j === n) {
res.push(i - n);
j = next[j - 1] + 1;
}
} else {
if (j === 0) {
i++;
} else {
j = next[j - 1] + 1;
}
}
}
return res;
}
let source = '21231212121231231231231232234121212312312312331212123',
match = 'abba';
let res = search(source, match);
console.log(res);
JS實現(xiàn)KMP算法
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來央勒，“玉大人不见，你說我怎么就攤上這事〈薏剑” “怎么了稳吮？”我有些...
- 文/不壞的土叔 我叫張陵，是天一觀的道長井濒。 經(jīng)常有香客問我灶似，道長，這世上最難降的妖魔是什么瑞你？ 我笑而不...
- 正文 為了忘掉前任酪惭，我火速辦了婚禮，結(jié)果婚禮上者甲，老公的妹妹穿的比我還像新娘春感。我一直安慰自己，他們只是感情好虏缸，可當我...
- 文/花漫 我一把揭開白布鲫懒。 她就那樣靜靜地躺著，像睡著了一般刽辙。 火紅的嫁衣襯著肌膚如雪窥岩。 梳的紋絲不亂的頭發(fā)上，一...
- 文/蒼蘭香墨 我猛地睜開眼集歇，長吁一口氣：“原來是場噩夢啊……” “哼桶略！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起诲宇，我...
- 正文 年R本政府宣布，位于F島的核電站型奥，受9級特大地震影響瞳收，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜厢汹，卻給世界環(huán)境...
- 文/蒙蒙 一螟深、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧烫葬，春花似錦界弧、人聲如沸。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽咽瓷。三九已至设凹，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間茅姜，已是汗流浹背闪朱。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- talk is cheap，show me the code： 參考鏈接： 阮一峰-字符串匹配的KMP算法[KMP...
- 1 需求分析 1.1 系統(tǒng)目標 實現(xiàn)題目說所要求的三種匹配算法的算法設(shè)計寓免，算法實現(xiàn)癣诱，程序能夠穩(wěn)定，準確的運行并實現(xiàn)...
- RAM（Random-access memory）在任何軟件開發(fā)中都是非常寶貴的資源袜香，移動操作系統(tǒng)由于其物理內(nèi)存的...
