report.tex

\documentclass[a4paper,11pt]{article}
\usepackage[margin=0.5in]{geometry}
\usepackage[utf8]{inputenc}
\usepackage[utf8]{vntex}
\usepackage{blindtext, amsfonts, amsmath, listings, color}
\usepackage{babel}
\usepackage{csvsimple} % For csv importing.
\usepackage[dvipsnames]{xcolor}
\usepackage{tvietlistings}	
\usepackage{array}


\makeatletter
\newcommand\docolumncount[2]{%
	\csvloop{
		file=#1,
		command=,
		after reading={\numdef\mycolumncount{\csv@columncount-1}},
	}%
}
\csvset{
	autotabularcenter/.style={
		file=#1,
		after head=\csv@pretable
		\begin{tabular}{|l|*{\mycolumncount}{>{\centering\arraybackslash}p{4.5cm}|}}\csv@tablehead,
			table head=\hline\csvlinetotablerow\\\hline,
			late after line=\\,
			table foot=\\\hline,
			late after last line=\csv@tablefoot
		\end{tabular}\csv@posttable,
		command=\csvlinetotablerow},
}
\makeatother
\newcommand{\csvautotabularcenter}[2][]{\csvloop{autotabularcenter={#2},#1}}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\definecolor{Ao}{rgb}{0.55, 0.71, 0.0}
% Phần biểu diễn
\lstset{frame=tb,
	language=TeX,
	aboveskip=3mm,
	belowskip=3mm,
	showstringspaces=false,
	basicstyle={\small\ttfamily},
	firstnumber=0,
	numbers=left,
	numberstyle=\tiny\color{gray},
	breaklines=true,
	captionpos=t,
	breakatwhitespace=true,
	tabsize=2,
	moredelim=**[is][\color{Ao}]{@}{@}
}

\title{TÌM KIẾM CHUỖI}
\author{
	Phan Lộc Sơn\\ 19120033
	\\[3ex]
	Đoàn Kim Huy\\ 19120239
	\\[3ex]
	Đỗ Hoài Nam \\ 19120296
	\\[3ex]
	Trần Anh Huy \\ 19120082
}
\date{\today}
\begin{document}
\makeatletter
\begin{titlepage}
	\begin{center}
		\vspace*{1cm}
		
		\Huge
		\textbf{TÌM KIẾM CHUỖI}
		
		\vspace{0.5cm}
		\LARGE
		Challenge 01
		
		\vspace{3.5cm}
		
		\@author

		\vfill	

		Cấu trúc Dữ liệu và Giải thuật\\
		19CNTN
		
		\vspace{0.8cm}
		
		\Large
		Khoa Công nghệ Thông tin\\
		Đại học Khoa học Tự nhiên\\
		Việt Nam\\
		23 - 11 - 2020
		
	\end{center}
\end{titlepage}

\makeatother
\tableofcontents
\part{TÌM KIẾM CHUỖI}

\section{Xác định vấn đề}
Tìm kiếm chuỗi hiện diện rất nhiều trong cuộc sống, ví dụ như: tìm tên thầy dạy DSA trong danh sách giảng viên,
tìm tên trong bảng điểm,.. hoặc trong khoa học, như là tìm liệu cấu trúc ADN của virus này có trong virus khác hay không.

Trong Tin học, các trình soạn thảo văn bản thường phải tìm kiếm (tất cả) các lần xuất hiện của một đoạn văn bản trong một văn bản dài. Thông thường văn bản được chỉnh sửa liên tục, và các phần văn bản cần tìm kiếm thì được nhập bởi người dùng. Việc phát minh ra các thuật toán tìm kiếm chuỗi hiệu quả đã giúp ích rất nhiều cho các bài toán kể trên.

Bài toán tìm kiếm chuỗi thường được mô tả theo mô hình sau: \\
Một chuỗi cần tìm kiếm S có dạng một chuỗi kí tự S[1..m], cần tìm chuỗi S trong một đoạn văn bản T[1..n], với m <= n. Đồng thời, tất cả các ký tự trong T và S đều thuộc về một tập hữu hạn các ký tự cho trước. Chuỗi S được gọi là xuất hiện bắt đầu từ vị trí p + 1 nếu thoả điều kiện: T[p + j] = S[j], với 1 <= j <= m.

\vspace*{3mm}
Có 3 thuật toán thường được dùng để tìm kiếm chuỗi:
\begin{itemize}
	\item Thuật toán Brute-force (vét cạn, hay còn gọi là thuật trâu)
	\item Rabin - Karp
	\item Knuth - Morris - Pratt
\end{itemize}
Chi tiết của từng thuật toán sẽ được trình bày bên dưới.

\section{Một số thuật toán tìm kiếm chuỗi}

	\subsection {Brute-force} 
			Giải thuật Brute-Force, hay còn gọi là vét cạn, 
		là thuật toán đơn giản nhất trong các thuật toán 
		tìm kiếm chuỗi con \textit{pattern} 
		trong chuỗi cha \textit{text}.

		Có thể giải thích đơn giản, giải thuật Brute-Force 
		so sánh lần lượt mỗi chuỗi con \textit{subtext} của \textit{text} 
		có cùng chiều dài với \textit{pattern} với \textit{pattern}, 
		nếu tìm được, trả về kết quả là vị trí được tìm thấy; khi không 
		tìm được kết quả mong muốn, trả về giá trị quy ước là không tìm thấy.

		Trong ví dụ sau, ta sẽ làm rõ cách hoạt động của giải thuật này:\\
		\textit{text} \hspace*{7mm}= \verb|Let them go!| \\
		\textit{pattern} \hspace*{0.1mm} = \verb|them| 
	% L
		\vspace*{4mm}
		\hrule
		\textcolor{red}{L}et them go!\
		
		\textcolor{red}{t}hem

		% Le
		\vspace*{2mm}
		\hrule
		L\textcolor{red}{e}t them go!
		
		\textcolor{white}{L}\textcolor{red}{t}hem
		
		% Let
		\vspace*{2mm}
		\hrule
		Le\textcolor{ForestGreen}{t} them go!
		
		\textcolor{white}{Le}\textcolor{ForestGreen}{t}hem
		
		% Let 
		\vspace*{2mm}
		\hrule
		Le\textcolor{ForestGreen}{t}\textcolor{red}{\textvisiblespace}them go!
		
		\textcolor{white}{Le}\textcolor{ForestGreen}{t}\textcolor{red}{h}em

		% Let 
		\vspace*{2mm}
		\hrule
		Let\textcolor{red}{\textvisiblespace}them go!
		
		\textcolor{white}{Let}\textcolor{red}{t}hem
		
		% Let t
		\vspace*{2mm}
		\hrule
		Let \textcolor{ForestGreen}{t}hem go!
		
		\textcolor{white}{Let }\textcolor{ForestGreen}{t}hem

		% Let th
		\vspace*{2mm}
		\hrule
		Let \textcolor{ForestGreen}{th}em go!
		
		\textcolor{white}{Let }\textcolor{ForestGreen}{th}em
		
		% Let the
		\vspace*{2mm}
		\hrule
		Let \textcolor{ForestGreen}{the}m go!
		
		\textcolor{white}{Let }\textcolor{ForestGreen}{the}m
					
		% Let them
		\vspace*{2mm}
		\hrule
		Let \textcolor{ForestGreen}{them} go!
		
		\textcolor{white}{Let }\textcolor{ForestGreen}{them}
		\vspace*{2mm}
		\hrule

		Ta tìm thấy chuỗi pattern tại vị trí thứ 4!
		
		\vspace*{4mm}
		
		Từ ví dụ trên, ta thiết kế mã giả cho giải thuật Brute-Force:

		\begin{lstlisting}
		function: Brute-Force String Matching
		text: chuỗi cha 
		pattern: chuỗi cần tìm 
		subtext: 1 đoạn thân của chuỗi cha có cùng chiều dài với pattern.
		Trả về: vị trí tìm thấy đầu tiên hoặc -1 nếu không tìm thấy.
		
			vị trí tìm thấy = -1
			subtext = chuỗi con đầu text có độ dài bằng pattern
			while (chưa tìm thấy hoặc chưa tới cuối text)
				if (từng ký tự của subtext = pattern):
					trả về vị trí
				else:
					dịch chuyển chuỗi con subtext trong text sang phải 1 chữ cái
			Trả về: vị trí tìm thấy
				\end{lstlisting}
		
		Với chuỗi \textit{pattern} có độ dài là M, chuỗi \textit{text} có độ dài là N \\
		Phân tích độ phức tạp của thuật toán trong trường hợp xấu nhất:
		\begin{itemize}
			\item Mỗi lần so sánh với \textit{subtext}, \textit{pattern} phải so sánh nhiều nhất là M lần (trong trường hợp cả M - 1 ký tự đầu đều đúng).
			\item Có tất cả N - M + 1 chuỗi, vậy số chuỗi cần so sánh nhiều nhất là N - M + 1 \textit{subtext} như vậy (trong trường hợp N - M + 2 chuỗi \textit{subtext} đầu không trùng với \textit{pattern})
			
			$\to$ Cần M(N - M + 1) lần. Vì duyệt tới cuối mảng nên đây là trường hợp tìm thấy ở cuối mảng, hoặc không tìm thấy\\
			$\to$ Cận trên $O(MN)$ (vì N > N - M + 1). \\
			$\to$ Cấp phát bộ nhớ: 0.
		\end{itemize}

		Phân tích độ phức tạp của thuật toán trong trường hợp tốt nhất:
		\begin{itemize}
			\item Trong trường hợp tốt nhất, có thể thấy \textit{pattern} chính là \textit{subtext} đầu tiên của \textit{text}.
			\item Như vậy, chỉ cần tốn M lần so sánh các ký tự.
			
			$\to$ Cần M lần. \\
			$\to$ Cận trên $O(M)$. \\
			$\to$ Cấp phát bộ nhớ: 0.
		\end{itemize}

		Độ phức tạp của thuật toán trong trường hợp trung bình: $O(MN)$
		
		Đánh giá:
		\begin{itemize}
			\item Dễ hiểu, thuật toán này chỉ duyệt từ đầu đến cuối, so sánh tuần tự từng chuỗi con với chuỗi cần tìm kiếm.
			\item Không cần bước tiền xử lý (như các thuật toán được trình bày bên dưới).
			\item Độ phức tạp $O(MN)$. Không cần xin thêm bộ nhớ.
		\end{itemize}

		\subsection {Rabin-Karp}
		
			Thuật toán Rabin-Karp là một thuật toán được sử dụng để tìm kiếm
			chuỗi con \textit{pattern} trong chuỗi cha \textit{text} bằng cách sử dụng một hàm băm.

			Hàm băm là một hàm chuyển đổi mọi chuỗi thành giá trị số, giá trị này được gọi là mã băm của nó. Ví dụ, chúng ta có thể có hàm băm hash("hello")=5.

			Giống như Thuật toán Brute-Force, thuật toán Rabin-Karp cũng dịch \textit{pattern} 
			qua từng phần tử trong \textit{text} để so sánh.
			Nhưng sự khác biệt là thuật toán Rabin-Karp so khớp mã băm của \textit{pattern} 
			với mã băm của chuỗi con \textit{subtext} của \textit{text}, và nếu mã băm khớp thì thuật toán sẽ so sánh từng ký tự trong 2 chuỗi với nhau.

			Nếu mã băm được biểu diễn bằng số nguyên không quá 64 bits, độ phức tạp thời gian (time-complexity) 
			của việc so sánh \textit{pattern} có độ dài m với \textit{subtext} có cùng độ dài giảm từ O(m) xuống O(1).

			Tuy nhiên mọi thứ đều có hai mặt, vấn đề của hàm băm đó là mã băm của hai chuỗi khác nhau có thể bằng nhau. 
			Ví dụ xét hàm băm hash(S) tính mã băm của xâu S bằng cách cộng mã ASCII của các kí tự trong S: hash("abcd")=97+98+99+100=394, hàm băm này quá đơn giản và có khả năng gây trùng mã băm cao: hash("dcba")=100+99+98+97=394, nhưng "abcd" $\neq$ "dcba".

			Một hàm băm tốt thoả mãn các điều kiện sau:
			\begin{itemize}
				\item Tính toán nhanh.
				\item Xác suất trùng mã băm nhỏ.
			\end{itemize}

			Thuật toán Rabin-Karp xây dựng hàm băm với ý tuởng cơ số: xem mọi xâu như là một chuỗi số với một cơ số (base) nào đó. Hàm băm đuợc tính tương tự như việc ta chuyển một số nguyên về giá trị của nó, nếu là xâu kí tự thì có thể sử dụng mã ASCII (hoặc UNICODE). Một số ví dụ:
			\begin{itemize}
			\item base=10, hash("425")=4×102+2×101+5×100=425.
			\item base=26, kí tự là chữ cái từ a đến z: hash("abc")=97×262+98×261+99×260=68219.
			\end{itemize}
			Để tránh tràn số thì kết quả trên đuợc chia lấy dư cho một số q, thường được chọn là một số nguyên tố lớn. Nếu gọi tập các kí tự được sử dụng trong chuỗi là $\sum$ thì base thừờng được chọn sao cho base=|$\sum$| hoặc là một số nguyên tố lớn.

			Độ phức tạp thời gian để tính mã băm của chuỗi độ dài k mất O(k). Khi hiện thực thuật toán, ta sẽ "trượt" \textit{pattern} có độ dài m trên \textit{text} từ vị trí 0 đến n-m để so sánh mã băm. Rolling hash là hàm băm có thể tính mã băm $h_i$ của \textit{text}[i... i+m-1] dựa trên mã băm $h_{i-1}$ của \textit{text}[(i-1)... (i+m)] chỉ trong thời gian O(1) thay vì tính lại trong thời gian O(m), từ đó tăng tính hiệu quả.

			$h_i=(base\times(h_{i-1}-base^{m-1}\times\textit{text}[i-1])+\textit{text}[i+m-1]) \% q$

			Trong ví dụ sau, ta sẽ làm rõ cách hoạt động của giải thuật này:\\
			Để đơn giản, ta chọn tập các kí tự được sử dụng trong chuỗi là \{a, b, c, d, e, f, g, h, i, j\} ứng với giá trị số lần lượt là \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\} và base=10, q=13.\\
			\textit{text} \hspace*{6mm}= abccddaefg\\
			\textit{pattern} \hspace*{0.3mm}= cdd\\
			Mã băm của \textit{pattern}: hash("cdd")=$(3\times10^2+4\times10^1+4\times10^0) \% 13=344 \% 13=6$
			
			\pagebreak
			\vspace*{4mm}
			\hrule
			\textcolor{ForestGreen}{abc}cddaefg \hspace*{0.6cm} // hash("abc")=$(1\times10^2+2\times10^1+3\times10^0) \% 13=123 \% 13=6$

			\textcolor{ForestGreen}{cdd} \hspace*{1.8cm} // Vì mã băm của \textit{subtext} "abc" và \textit{pattern} bằng nhau \\
		\hspace*{2.5cm} // nên thuật toán so sánh từng ký tự của chúng.\\
		\hspace*{2.5cm} // Do "abc"$\neq$\textit{pattern} nên dịch \textit{pattern} qua phải 1 phần tử để tiếp tục tìm kiếm.

			\vspace*{2mm}
			\hrule
			a\textcolor{ForestGreen}{bcc}ddaefg \hspace*{0.6cm} // hash("bcc")=$(10\times(123-10^2\times1)+3)\%13=233\%13=12$
			
			\textcolor{white}{a}\textcolor{ForestGreen}{cdd} \hspace*{1.6cm} // Vì mã băm của \textit{subtext} "bcc" và \textit{pattern} khác nhau \\
		\hspace*{2.5cm} // nên dịch \textit{pattern} qua phải 1 phần tử để tiếp tục tìm kiếm.

			\vspace*{2mm}
			\hrule
			ab\textcolor{ForestGreen}{ccd}daefg \hspace*{0.6cm} // hash("ccd")=$(10\times(233-10^2\times2)+4)\%13=334\%13=9$
			
			\textcolor{white}{aa}\textcolor{ForestGreen}{cdd} \hspace*{1.4cm} // Vì mã băm của \textit{subtext} "ccd" và \textit{pattern} khác nhau \\
		\hspace*{2.5cm} // nên dịch \textit{pattern} qua phải 1 phần tử để tiếp tục tìm kiếm.

			\vspace*{2mm}
			\hrule
			abc\textcolor{ForestGreen}{cdd}aefg \hspace*{0.6cm} // hash("cdd")=$(10\times(334-10^2\times3)+4)\%13=344\%13=6$
			
			\textcolor{white}{aaa}\textcolor{ForestGreen}{cdd} \hspace*{1.2cm} // Vì mã băm của \textit{subtext} "ccd" và \textit{pattern} bằng nhau \\
		\hspace*{2.5cm} // nên thuật toán so sánh từng ký tự của chúng.\\
		\hspace*{2.5cm} // Do "abc"$=$\textit{pattern} nên chuỗi đã được tìm thấy.

		\vspace*{2mm}
		\hrule
		\vspace*{4mm}
		Từ ví dụ trên, ta thiết kế mã giả cho giải thuật Rabin-Karp:

			\begin{lstlisting}
			function: Rabin-Karp String Matching
			text: chuỗi cha 
			pattern: chuỗi cần tìm 
			subtext: 1 đoạn thân của chuỗi cha có cùng chiều dài với pattern.
			Trả về: vị trí tìm thấy đầu tiên hoặc -1 nếu không tìm thấy.
			
				n=chiều dài chuỗi text
				m=chiều dài chuỗi pattern
				Tính mã băm của pattern và chuỗi con đầu text có độ dài bằng pattern
				Dịch pattern từ vị trí 0, qua từng phần tử của text đến vị trí n-m
					Kiểm tra mã băm của subtext hiện tại và pattern
						Nếu bằng nhau, so sánh từng ký tự trong 2 chuỗi
							Nếu hoàn toàn giống nhau, trả về vị trí
					Tính mã băm của subtext tiếp theo, nếu âm cộng thêm một lượng q
				Nếu trong vòng lặp không tìm thấy pattern, ta đã duyệt hết text, trả về -1 báo kết quả không tìm thấy pattern trong text.
			\end{lstlisting}

			Với chuỗi \textit{pattern} có độ dài là M, chuỗi \textit{text} có độ dài là N: \\
			Phân tích độ phức tạp của thuật toán:

				Trong quá trình tiền xử lý, để tính mã băm cho \textit{pattern} cần duyệt qua M phần tử, tương tự với \textit{subtext} đầu tiên \textit{text}, vậy độ phức tạp là $O(M+M) \in O(M)$.

				Trường hợp tốt nhất, có thể thấy \textit{pattern} chính là \textit{subtext} đầu tiên của \textit{text}, khi đó chỉ cần tốn M lần so sánh các ký tự, kết hợp với quá trình tiền xử lý nên độ phức tạp là $O(M+M) \in O(M)$.

				Trường hợp xấu nhất:
			\begin{itemize}
				\item Mỗi lần so sánh với \textit{subtext}, \textit{pattern} phải so sánh nhiều nhất là M lần (trong trường hợp mã băm bằng nhau và cả M - 1 ký tự đầu đều đúng).
				\item Có tất cả N - M + 1 chuỗi, vậy số chuỗi cần so sánh nhiều nhất là N - M + 1 \textit{subtext} như vậy (trong trường hợp chuỗi cần tìm nằm cuối, N - M + 2 chuỗi \textit{subext} đầu không trùng với \textit{pattern}).
				
				$\to$ Cần nhiều nhất M(N - M + 1) lần so sánh. Vì duyệt tới cuối chuỗi nên đây là trường hợp tìm thấy ở cuối hoặc không tìm thấy và xảy ra trùng mã băm ở tất cả lần so sánh trước đó.\\
				$\to$ Cận trên $O(MN)$ (vì N > N - M + 1). 
				
				Trường hợp trung bình: $O(N+M) \in O(M)$
			\end{itemize}
				Do trong quá trình tìm kiếm có thực hiện tính toán và lưu mã băm nên chi phí bộ nhớ là hằng số $O(1)$.
			Đánh giá:
			\begin{itemize}
				\item Mặc dù trong trường hợp xấu nhất độ phức tạp là $O(MN)$ không tốt hơn giải thuật Brute-Force, nhưng giải thuật Rabin-Karp hoạt động tốt hơn nhiều trong trường hợp trung bình và thực tế.
				\item Có bước tiền xử lý với độ phức tạp $O(M)$ trước khi bắt đầu tìm kiếm.
				\item Độ phức tạp $O(MN)$. Chi phí bộ nhớ $O(1)$.
			\end{itemize}
		\subsection {Knuth-Morris-Pratt}
		
			Giải thuật Knuth-Morris-Pratt, về cơ bản cũng giống như thuật toán Brute-Force, 
			tuy nhiên, chỉ khác ở chỗ, Brute-Forch khi so sánh \textit{pattern} và \textit{subtext}, Brute-Force so sánh toàn bộ 
			các ký tự của chúng lại từ đầu, còn Knuth-Morris-Pratt, từ lần so sánh trước, sẽ quyết định có so sánh pattern với \textit{subtext} kế tiếp không, 
			và nếu không sẽ shift bao nhiêu bước để đến lượt so sánh tiếp theo.

			Để dễ hiểu, ta xét 1 ví dụ như sau: 
			
			\textit{text} \hspace*{6mm}= ababcababd

			\textit{pattern} \hspace*{0.3mm}= ababd\\
			Quy ước vị trí ký tự đầu tiên trong chuỗi là 1.\\
			Đầu tiên, tính giá trị của mảng Failure Function:\\
			Failure Function tại vị trí i là độ dài của chuỗi thoả mãn:
			\begin{itemize}
				\item Chuỗi phải là dài nhất có thể.
				\item Là chuỗi prefix của text[0, i].
				\item Là chuỗi suffix của text[1, i].
			\end{itemize}
			Như vậy ta tính được: 
			f = [0, 0, 1, 2, 0]
			
			% L
			\vspace*{4mm}
			\hrule
			\textcolor{ForestGreen}{a}babcababd
			
			\textcolor{ForestGreen}{a}babd \hspace*{1.8cm} // Bắt đầu so sánh tương tự giải thuật Brute-Force.

			% Le
			\vspace*{2mm}
			\hrule
			\textcolor{ForestGreen}{ab}abcababd
			
			\textcolor{ForestGreen}{ab}abd
			
			% Le
			\vspace*{2mm}
			\hrule
			\textcolor{ForestGreen}{aba}bcababd
			
			\textcolor{ForestGreen}{aba}bd

			% Le
			\vspace*{2mm}
			\hrule
			\textcolor{ForestGreen}{abab}cababd
			
			\textcolor{ForestGreen}{abab}d

			% Let 
			\vspace*{2mm}
			\hrule
			\textcolor{ForestGreen}{abab}\textcolor{red}{c}ababd
			
			\textcolor{ForestGreen}{abab}\textcolor{red}{d}			\hspace*{1.2cm} // Không khớp nhau, shift sang phải để tìm kiếm \\
																	\hspace*{2.9cm} // So sánh thất bại ở vị trí thứ 5, ta chú ý tới f[4] = 2 > 0 \\
																	\hspace*{2.9cm} // KMP nói rằng để tối ưu hoá thời gian, ta cần shift tiếp 2 bước.\\
																	\hspace*{2.9cm} // Để ý rằng f[2] = 0, nên ký tự 1 khác ký tự 2 \\  
																	\hspace*{2.9cm} // Mà pattern[1] = text[1], pattern[2] = text[2], pattern[1] != pattern[2] \\ 
																	\hspace*{2.9cm} // => pattern[1] != text[2] => Việc shift 1 bước rồi so sánh là dư thừa.

			\vspace*{2mm}
			\hrule
			ab\textcolor{ForestGreen}{ab}\textcolor{red}{c}ababd
			
			\textcolor{white}{ab}\textcolor{ForestGreen}{ab}\textcolor{red}{a}bd 			\hspace*{0.8cm} // Vì ta đã biết f[4] = 2 -> pattern[1, 2] = pattern[3, 4] \\
																							\hspace*{2.9cm} // Ở lượt trước, ta có pattern[1, 2] = text[1, 2] và pattern[3, 4] = text[3, 4] \\
																							\hspace*{2.9cm} // Ngoài ra, vừa rồi ta shift 2 bước -> pattern[1, 2] = text[3, 4]\\
																							\hspace*{2.9cm} // Tức là ta không cần so sánh 2 ký tự đầu ở lượt này\\
																							\hspace*{2.9cm} // Vị trí không khớp là \textit{pattern}[3], cùng với f[2] = 0 nên \\
																							\hspace*{2.9cm} // Bước tiếp theo cần shift sang phải 1 ký tự để tiếp tục so sánh.

			\vspace*{2mm}
			\hrule
			aba\textcolor{red}{b}cababd
			
			\textcolor{white}{aba}\textcolor{red}{a}babd 						\hspace*{1.2cm} // Tiếp tục so sánh \textit{pattern} với \textit{text} tương tự giải thuật Brute-Force. 

			\vspace*{2mm}
			\hrule
			abab\textcolor{red}{c}ababd
			
			\textcolor{white}{abab}\textcolor{red}{a}babd 		

			\vspace*{2mm}
			\hrule
			ababc\textcolor{ForestGreen}{a}babd
			
			\textcolor{white}{ababc}\textcolor{ForestGreen}{a}babd 

			\vspace*{2mm}
			\hrule
			ababc\textcolor{ForestGreen}{ab}abd
			
			\textcolor{white}{ababc}\textcolor{ForestGreen}{ab}abd 

			\vspace*{2mm}
			\hrule
			ababc\textcolor{ForestGreen}{aba}bd
			
			\textcolor{white}{ababc}\textcolor{ForestGreen}{aba}bd 

			\vspace*{2mm}
			\hrule
			ababc\textcolor{ForestGreen}{abab}d
			
			\textcolor{white}{ababc}\textcolor{ForestGreen}{abab}d 

			\vspace*{2mm}
			\hrule
			ababc\textcolor{ForestGreen}{ababd}
			
			\textcolor{white}{ababc}\textcolor{ForestGreen}{ababd} 				\hspace*{0.8cm} // \textit{pattern} khớp \textit{subtext} tại vị trí thứ 6 của \textit{text}\\
															\hspace*{2.9cm} // Vị trí tìm được là 6, kết thúc tìm kiếm.
			
			\vspace*{2mm}
			\hrule			
					
			Từ ví dụ trên, ta tìm cách thiết kế ý tưởng của KMP để tìm chuỗi 1 cách tổng quát:
			\begin{itemize}
				\item Ta thấy rằng, để KMP hoạt động, cần phải xử lý trước pattern, chính là tìm Failure Function
				\item Trong khi tìm kiếm chuỗi, ta có thể dùng 2 biến i và j dùng để duyệt qua text và pattern để so sánh các ký tự trong chúng: \\
				1. Nếu pattern[j] = text[i], tăng thêm i và j để so sánh ký tự kế tiếp. \\
				2. Nếu pattern[j] $\neq$ text[i], và j = 1, tức là ký tự đầu của chúng khác nhau, ta chỉ cần shift chuỗi so sánh chuỗi con kế tiếp.\\
				3. Nếu pattern[j] $\neq$ text[i], và j > 1, tức là đã có 1 lượng j - 1 ký tự ở trước đã được so sánh đúng, ta lấy f[i - 1] 
				và và shift chuỗi với số bước là min((i - 1) - f[i - 1], 1) để chuẩn bị cho lượt so sánh kế tiếp.
			\end{itemize}
			
			Từ ý tưởng trên, ta xây dựng mã giả cho thuật toán KMP:

			\begin{lstlisting}
			function: Build Failure Function
			pattern: chuỗi cần tìm 
			Trả về: Mảng f lưu độ dài lớn nhất f[i] của chuỗi chung prefix và suffix của pattern[1, i].

				f[] = 0 để lưu mảng trả về
				fpre = 0;   // lưu f[i - 1] trong vòng lặp bên dưới
				i = 2;		@// Ta chỉ tính f[2] trở đi, f[1] luôn bằng 0@
				while (i <= n)		
					Nếu pattern[i] == pattern[f[i - 1] + 1]
						fpre++
						f[i] = fpre	@// tận dụng kết i - 1 kết quả so sánh của f[i - 1], ta chỉ cần so sánh 1 ký tự.@
						i++
					Nếu pattern[i] != pattern[f[i - 1] + 1] và f[i - 1] = 0
						@// Tức là suffix và prefix là chuỗi có độ dài f[i - 1] + 1 có ký tự cuối không giống@
						@// -> f[i] = 0@
						f[i] = 0
						i++
					Nếu pattern[i] != pattern[f[i - 1] + 1] và f[i - 1] > 0
						@// Trường hợp này, có thể f[i] = f[i - 1]@
						@// Ta sẽ tận dụng pattern[1, f[i- 1]] = pattern[i - f[i-1], i]@
						@// Và f[f[j]] (độ dài này lớn nhất là j - 1)@
						@// Ví dụ AAABAAAA khi xét i = 8, ta lợi dụng chuỗi [AA]ABAAAA = A[AA]BAAAA và [AAA]BAAAA = AAAB[AAA]A@
						@// Suy ra được [AA]ABAAAA = A[AA]BAAAA = AAABA[AA]A@
						@// Như thế chỉ cần xét ký tự AA[A]BAAAA và AAABAAA[A] để xác định f[i]@
						fpre = f[fpre]
				Trả về: f[]

			function: KMP String Matching
			text: chuỗi cha 
			pattern: chuỗi cần tìm 
			Trả về: vị trí tìm thấy đầu tiên hoặc -1 nếu không tìm thấy.

				i = 1; j = 1; 
				while (i < len(text) - len(pattern))
					Nếu pattern[j] == text[i]
						Tiếp tục i++ và j++ và so sánh
							Nếu j = len(pattern) trả về đã tìm thấy pattern tại vị trí i - j.
					Nếu pattern[j] != text[i] và j == 1
						i = i + 1  @// shift sang phải 1 bước @
					Nếu pattern[j] != text[i] và j > 1
						j = f[i] và tiếp tục so sánh text[i] và pattern[j] 
				Nếu trong vòng lặp không tìm thấy pattern, ta đã duyệt hết text, trả về -1 báo kết quả không tìm thấy pattern trong text.
					\end{lstlisting}
			
			Với chuỗi \textit{pattern} có độ dài là M, chuỗi \textit{text} có độ dài là N \\
			Phân tích độ phức tạp của thuật toán trong trường hợp xấu nhất:
			\begin{itemize}
				\item Trong quá trình tiền xử lý (tính hàm Failure Function), trong vòng while chỉ tốn nhiều nhất 1 - 2 lần để tính f[i], vậy độ 
				phức tạp là $O(M)$
				\item Trong quá trình so sánh, mỗi lần, ta hoặc sẽ tăng i lên 1 đơn vị, hoặc sẽ giảm j ít nhất 1 đơn vị, nghĩa là tăng k lên 1 đơn vị, với k = i - j < N.
				Vậy tổng cộng trong vòng lặp có thể lặp < 2n lần (i và k không thể vượt quá N), như vậy độ phức tạp là $O(2N)$.\\
				$\to$ Độ phức tạp $O(M + N)$.\\
				$\to$ Cấp phát bộ nhớ: $O(M)$.
			\end{itemize}

			Phân tích độ phức tạp của thuật toán trong trường hợp tốt nhất:
			\begin{itemize}
				\item Trong trường hợp tốt nhất, có thể thấy \textit{pattern} chính là \textit{subtext} đầu tiên của \textit{text}.
				\item Như vậy, chỉ cần tốn M lần so sánh các ký tự. Ngoài ra còn tốn thêm chi phí tính Failure Function $O(M)$.\\
				$\to$ Cận trên $O(M)$. \\
				$\to$ Cấp phát bộ nhớ: $O(M)$.
			\end{itemize}

			Độ phức tạp của thuật toán trong trường hợp trung bình:
			\begin{itemize}
				\item Cận trên $O(N + M)$.
				\item Cấp phát bộ nhớ: $O(M)$.
			\end{itemize}

			Đánh giá:
			\begin{itemize}
				\item Nhanh, chi phí tuyến tính.
				\item Phải xử lý trước khi tìm kiếm thực sự.
				\item Độ phức tạp $O(M + N)$. Chi phí bộ nhớ $O(M)$.
			\end{itemize}

	\section{So sánh các thuật toán tìm kiếm chuỗi}
\begin{center}
 \begin{tabular}{||m{4cm} | m{4cm} m{4cm}||} 
 \hline
 Thuật toán & Tiền xử lý & Tìm kiếm \\ [1ex] 
 \hline\hline
 Brute-Force & $0$ & $O((n-m+1)m)$ \\ [1ex] 
 \hline
 Rabin-Karp & $\Theta(m)$ & $O((n-m+1)m)$ \\ [1ex] 
 \hline
 Knuth-Morris-Pratt & $\Theta(m)$ & $\Theta(n)$ \\ [1ex] 
 \hline
\end{tabular}
\end{center}

Ngoại trừ thuật toán Brute-Force, hai thuật toán còn lại đều có bước tiền xử lý trước khi bắt đầu tìm kiếm. Thời gian chạy của từng thuật toán là tổng của thời gian tiền xử lý và thời gian tìm kiếm.

			\begin{itemize}
				\item Do không có bước tiền xử lý, thuật toán Brute-Force chạy khá chậm khi phải so sánh lần lượt từng vị trí trong chuỗi.
				\item Mặc dù trong trường hợp xấu nhất, thuật toán Rabin-Karp cũng không nhanh hơn Brute-Force nhưng trong thực tế lại hoạt động hiệu quả với độ phức tạp tuyến tính.
				\item Knuth-Morris-Pratt là thuật toán tốt nhất trong 3 thuật toán nêu trên vì có độ phức tạp tuyến tính trong tất cả trường hợp (khắc phục được điểm yếu của Rabin-Karp khi gặp trường hợp xấu nhất).
			\end{itemize}
	
	\part{TÌM KIẾM CHUỖI TRONG TIN HỌC}
	\Large {Ví dụ về Crossword game}
	\setcounter{section}{0}
	\section{Hướng giải Crossword game}

	Trong phần này, nhóm chúng tôi quyết định sẽ sử dụng thuật toán KMP để làm giải thuật tìm kiếm chuỗi, bởi vì giải thuật này có vẻ nhanh hơn 2 giải thuật còn lại với thời gian $O(M + N)$.

	Thuật toán chính của chương trình là đọc mảng chữ cái vào mảng \textbf{table} để tìm theo hàng ngang, và tạo mảng \textbf{Transpose\_table} bằng cách chuyển vị mảng \textbf{table} để tìm theo hàng dọc.

	Tìm bằng thuật toán KMP, hàng ngang trước và hàng dọc sau, nếu tìm thấy, in ra vị trí tìm thấy, nếu không, in ra NF.

	Độ phức tạp:
	\begin{itemize}
		\item Có H hàng, mỗi hàng cần tìm 1 chuỗi có độ dài M trong chuỗi W, vậy độ phức tạp là $O(H*(M + W))$.
		\item Có W cột, mỗi cột cần tìm 1 chuỗi có độ dài M trong chuỗi H, vậy độ phức tạp là $O(W*(M + H))$.
		\\$\to$ Như vậy, độ phức tạp là: $O(2WH + M(H + W))$ đối với từng từ cần tìm kiếm.
	\end{itemize}
	\section{Một số mẫu kiểm tra lời giải}
	Dưới đây là bảng số liệu nhóm chúng tôi đã thực hiện trên các tập dữ liệu $n \times n$: 5, 10, 20, 50:

	\begin{itemize}
	\docolumncount{Data/Random.csv}{\mycolumncount}
	\item Bộ dữ liệu ngẫu nhiên:
	
	\begin{center}
		\csvautotabularcenter{Data/Random.csv}\\
		Bảng 1: Số liệu với bộ test được sinh ngẫu nhiên, đơn vị micro second.
		\end{center}

	Nhận xét: Ở các bộ dữ liệu nhỏ, Naive nhanh hơn Rabin-Karp và Knuth-Morris-Pratt vì không có bước tiền xử lý.

	\item Bộ dữ liệu xấu nhất:
	\begin{center}
	
		\csvautotabularcenter{Data/Worse.csv}\\
		Bảng 2: Bảng số liệu với bộ test được sinh xấu nhất, đơn vị micro second.
	\end{center}

	Nhận xét: Tại bộ dữ liệu xấu nhất, Knuth-Morris-Pratt và Rabin-Karp nhanh hơn Naive\\
	Ngoài ra, càng tăng size bộ dữ liệu, tốc độ tăng thời gian của Naive > Rabin-Karp > Knuth-Morris-Pratt (Naive tăng nhanh nhất, Knuth-Morris-Pratt tăng chậm nhất)
	\end{itemize}

\begin{thebibliography}{99}
\bibitem{Introduction to Algorithms} 
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, 
2009
\textit{Introduction to Algorithms (3rdedition)}. 
Massachusetts Institute of Technology

\bibitem{RK website 1} 
Rabin-Karp Algorithm,
\\texttt{https://www.programiz.com/dsa/rabin-karp-algorithm}

\bibitem{RK website 2} 
Rabin-Karp Algorithm for Pattern Searching,
\\texttt{https://www.geeksforgeeks.org/rabin-karp-algorithm-for-pattern-searching}
\end{thebibliography}

\end{document}