local concat = table.concat
local tree = {}

local function tree_add(str)
	local p = tree
	for i = 1, #str do
		local c = str:byte(i)
		local n = p[c]
		if not n then
			n = {}
			p[c] = n
		end
		p = n
	end
	p.isleaf = true
end

local function tree_route(str, i)
	local p = tree
	local greedy = -1
	while i <= #str do
		local c = str:byte(i)
		p = p[c]
		if not p then
			break
		elseif p.isleaf then
			greedy = i
		end
		i = i + 1
	end
	return greedy
end

local function tree_match(str, func)
	local buf
	local i = 1
	local last = 1
	while i <= #str do
		local start = i
		i = tree_route(str, i)
		if i >= start then
			if not buf then
				buf = {}
			end
			print("sub:", str:sub(last, start - 1))
			buf[#buf + 1] = str:sub(last, start - 1)
			buf[#buf + 1] = func(str, start, i)
			last = i + 1
		else
			i = start
		end
		i = i+1
	end
	if buf then
		buf[#buf + 1] = str:sub(last)
		return concat(buf)
	else
		return str
	end
end

local function tree_detect(str, ban)
	local i = 1
	local count = 0
	while i <= #str do
		local start = i
		i = tree_route(str, i)
		if i >= start then
			count = count + 1
			ban[start] = i
		else
			i = start
		end
		i = i+1
	end
	return count
end