Chap10. Dynamic Programming(DP)

Computation time

Step 4::s tableを使用して最適解を作成

PRINT-OPTIMAL-PARENS(s,i,j)
if i=j		// base case
	then print "A_i"
else print "("
	PRINT-OPTIMAL-PARENS(s,i,s[i,j])	// A_i,...,A_k	left child
   	 PRINT-OPTIMAL-PARENS(s,s[i,j]+1,j)	// A_{k+1},...,A_j	right child
    	print ")"

recursion tree
(A1((A2A3)A4))
NorderTraversal

binary propertyにn個の葉がある場合、内部ノードはn−1個の特徴を有する.
再帰ツリーのノード総数は2 n-1
従って、O(n)回
s tableを使い続けるのでO(ny 2 ny^2 ny 2)space

Chap11. String Matching

String Matching(=Pattern Matching)
長い文字列のテキストと短い文字列のPatternが現れる位置でナビゲートする問題

Pattern matching algorithms

1. Brute-force algorithm

Strings

Examples: C++ program, HTML document, DNA sequence, Digitized image
aアルファベットsigma:文字列に現れる可能性のある文字を定義する
任意の大きさ(長さ)mのString Pを有する場合、P[0,m-1]

substring:mより小さい任意のインデックスiからjまでの連続グラフ、P[i,j]

prefix:始点固定P[0、i]*proper prefix:真接頭辞

接尾辞:終了位置固定のP[i,m-1]*proper接尾辞:真接尾辞

String T(text)とP(pattern)が与えられた場合、PのTのsubstringに一致する
Examples: text editors, search engines, biological research

Brute-force algorithm

一致を検出またはすべての場合に実行
Basic operation:TとP文字の比較
一致しない場合は、パターンを右に移動して文字を比較します.

Algorithm BruteForceMatch(T, P)
	Input text T of size n and pattern 
		P of size m
	Output starting index of a substring of T equal to P 
		or -1 if no such substring exists
	for i <- 0 to n - m{ test shift i of the pattern }
		j <- 0
		while j < m ^ T[i + j] = P[j]
			j <- j + 1
		if j = m
			return i {match at i}
	return -1 {no match anywhere}

最悪:テキストの末尾に不一致が発生した場合、-sigmaは小さい
O(nm) times