計算機科学 – String Matching 文字列照合– (PDF)

計算機科学 – String Matching 文字列照合 – Yoshitsugu Yamamoto 山本 芳嗣 3F1007 (029-853-5001), 3E410 (029-853-5395) yamamoto@sk.tsukuba.ac.jp revised January 2006 T [s + 1..s + m] P [1.. m] s+1s s+m T 1 1 定義 Σ：finite alphabet 有限アルファベット、Σ = {0, 1}, {0, 1, 2, . . . , 9}, {a, b, c, . . . , z} Σ∗ ：set of all finite length strings of characters in Σ、アルファベットの有限長さの列の全体 T = T[1..n] ∈ Σ∗ ：text、テキスト P = P[1..m] ∈ Σ∗ ：patt

[mwsoft]

丁寧。オートマトン、ボイヤー−ムーア、ラビン−カープ等

[hiromark]

これはうれしい。