Algoritm haqda tushuncha

j	0	1	2	3	4
5
pat.charAt(J)	A	B	A	B	A	C
A	1	1	3	1	5	1
B	0	2	0	4	0	4
C	0	0	0	0	0	6

Bizda quyidagi matn mavjud: AABACAABABACAA
Pattern esa yuqorida ko’rib o’tganimiz: ABABAC
Matn ichidan patternni topishimiz kerak bo’lsin. Qidiruvni 0-holatdan boshlaymiz.
AABACAABABACAA
1-holatga o’tadi.
AABACAABABACAA
1-holatda qoladi.
AABACAABABACAA
2-holatga o’tadi.
AABACAABABACAA
3-holatga o’tadi.
AABACAABABACAA
0-holatga qaytadi.
AABACAABABACAA
1-holatga o’tadi.
AABACAABABACAA
1-holatda qoladi.
AABACAABABACAA
2-holatga o’tadi.
AABACAABABACAA
3-holatga o’tadi.
AABACAABABACAA
4-holatga o’tadi.
AABACAABABACAA
5-holatga o’tadi.
AABACAABABACAA
6-holatga o’tadi.
Pattern topildi. Qidiruv tugaydi.
Holatlarning o’zgarishini graph va jadvalga qarab boshqatdan ko’rib chiqishingiz mumkin.
Pattern’dan DFAni yasash
Yuqoridagi jadval va graph’ni biz o’zimi ko’rib turib yasadik. Kodda qanday qilib berilgan pattern’dan DFAni yasaymiz?
DFAni yasashda ikki xil holat bor:
Mos kelish. j-holatida, keyingi belgi c == pattern.charAt(j) bo’lsa, u holda j ni bittaga oshiramiz.
Mos kelmaslik. j-holatida, keyingi belgi c != pattern.charAt(j) bo’lsa, u holda ohirgi j-1 belgilar pattern[1..j-1] ichida bo’ladi.

	function dfaGenerator(pattern) {
	R = 128
	const M = pattern.length
	const dfa = [...Array(R).fill(null)].map(() => Array(M).fill(0))
	dfa[pattern.charCodeAt(0)][0] = 1
	for (let x = 0, j = 1; j < M; j++) {
	for (let c = 0; c < R; c++) {
	// Copy mismatched cases
	dfa[c][j] = dfa[c][x]
	// Set match case
	dfa[pattern.charCodeAt(j)][j] = j + 1
	// Update restart state
	x = dfa[pattern.charCodeAt(j)][x]
	}
	}
	return dfa
	}

view rawdfa-generator.js hosted with  by GitHub
Knuth-Morris-Pratt algoritmini kodda ifodalash

	function KMPSearch(str, pattern) {
	const N = str.length
	const M = pattern.length
	const dfa = dfaGenerator(pattern)
	let i, j
	if (!N || !M) {
	return -1
	}
	for (i = 0, j = 0; i < N && j < M; i++) {
	j = dfa[str.charCodeAt(i)][j]
	}
	if (j === M) {
	return i - M
	} else {
	return N
	}
	function dfaGenerator(pattern) {
	R = 128
	const M = pattern.length
	const dfa = [...Array(R).fill(null)].map(() => Array(M).fill(0))
	dfa[pattern.charCodeAt(0)][0] = 1
	for (let x = 0, j = 1; j < M; j++) {
	for (let c = 0; c < R; c++) {
	// Copy mismatched cases
	dfa[c][j] = dfa[c][x]
	// Set match case
	dfa[pattern.charCodeAt(j)][j] = j + 1
	// Update restart state
	x = dfa[pattern.charCodeAt(j)][x]
	}
	}
	return dfa
	}
	}
	/**
	* USAGE
	*/
	console.log(KMPSearch('AABACAABABACAA', 'ABABAC'))