;============================================================
;  アルゴリズム 06〜10: 文字列検索
;    06. 愚直 find (Naive)
;    07. KMP 文字列検索
;    08. Boyer-Moore (bad char)
;    09. Rabin-Karp (rolling hash)
;    10. StrRev (reverse string - bonus)
;============================================================

#include "hsp3cl_net_64.as"

; ----- 06. Naive -----
#module
#defcfunc naive_find var _hay, var _pat, \
	local _n, local _m, local _i, local _j, local _match
	_n = strlen(_hay) : _m = strlen(_pat)
	if _m == 0 : return 0
	repeat _n - _m + 1
		_i = cnt
		_match = 1
		repeat _m
			_j = cnt
			if peek(_hay, _i + _j) != peek(_pat, _j) : _match = 0 : break
		loop
		if _match : return _i
	loop
	return -1
#global

; ----- 07. KMP -----
#module
#defcfunc kmp_find var _hay, var _pat, \
	local _n, local _m, local _i, local _j
	_n = strlen(_hay) : _m = strlen(_pat)
	if _m == 0 : return 0
	if _m > _n : return -1
	dim lps, _m
	_j = 0
	repeat _m - 1
		_i = cnt + 1
		repeat
			if _j <= 0 : break
			if peek(_pat, _i) == peek(_pat, _j) : break
			_j = lps(_j - 1)
		loop
		if peek(_pat, _i) == peek(_pat, _j) : _j++
		lps(_i) = _j
	loop
	_i = 0 : _j = 0
	repeat
		if _i >= _n : return -1
		if peek(_hay, _i) == peek(_pat, _j) {
			_i++ : _j++
			if _j == _m : return _i - _j
		} else {
			if _j > 0 : _j = lps(_j - 1) : else : _i++
		}
	loop
#global

; ----- 08. Boyer-Moore (bad char) -----
#module
#defcfunc bm_find var _hay, var _pat, \
	local _n, local _m, local _i, local _j, local _shift, local _c, local _found
	_n = strlen(_hay) : _m = strlen(_pat)
	if _m == 0 : return 0
	if _m > _n : return -1
	dim _bad, 256
	repeat 256 : _bad(cnt) = -1 : loop
	repeat _m : _bad(peek(_pat, cnt)) = cnt : loop
	_i = 0
	repeat
		if _i > _n - _m : return -1
		_j = _m - 1
		_found = 1
		repeat
			if _j < 0 : break
			if peek(_pat, _j) != peek(_hay, _i + _j) : _found = 0 : break
			_j--
		loop
		if _found : return _i
		_c = peek(_hay, _i + _j)
		_shift = _j - _bad(_c)
		if _shift < 1 : _shift = 1
		_i += _shift
	loop
#global

; ----- 09. Rabin-Karp -----
#module
#defcfunc rabin_karp var _hay, var _pat, \
	local _n, local _m, local _i, local _h, local _ph, local _hh, local _BASE, local _MOD, \
	local _ok
	_BASE = 131 : _MOD = 2147483647
	_n = strlen(_hay) : _m = strlen(_pat)
	if _m == 0 : return 0
	if _m > _n : return -1
	_ph = 0 : _hh = 0 : _h = 1
	repeat _m - 1 : _h = _h * _BASE \ _MOD : loop
	repeat _m
		_ph = (_ph * _BASE + peek(_pat, cnt)) \ _MOD
		_hh = (_hh * _BASE + peek(_hay, cnt)) \ _MOD
	loop
	repeat _n - _m + 1
		_i = cnt
		if _ph == _hh {
			_ok = 1
			repeat _m
				if peek(_pat, cnt) != peek(_hay, _i + cnt) : _ok = 0 : break
			loop
			if _ok : return _i
		}
		if _i < _n - _m {
			_hh = ((_hh - peek(_hay, _i) * _h) * _BASE + peek(_hay, _i + _m)) \ _MOD
			if _hh < 0 : _hh += _MOD
		}
	loop
	return -1
#global

; ----- 10. String reverse -----
#module
#deffunc str_reverse var _s, var _out, local _n, local _i
	_n = strlen(_s)
	sdim _out, _n + 1
	repeat _n
		_i = _n - 1 - cnt
		poke _out, cnt, peek(_s, _i)
	loop
	poke _out, _n, 0
	return
#global

; ===== デモ =====
	mes "=== 文字列検索 ==="
	hay = "ABAAABCDABAABCABAB"
	pat = "ABAB"
	mes "hay = " + hay
	mes "pat = " + pat
	mes strf("Naive(hay, pat) = %d",       naive_find(hay, pat))
	mes strf("KMP(hay, pat) = %d",         kmp_find(hay, pat))
	mes strf("BoyerMoore(hay, pat) = %d",  bm_find(hay, pat))
	mes strf("Rabin-Karp(hay, pat) = %d",  rabin_karp(hay, pat))

	mes ""
	s = "Hello, World!"
	str_reverse s, r
	mes strf("reverse('%s') = '%s'", s, r)
	end 0