Views
Document
Event
File
Folder
Image
Link
News Item
Photo
Photo Album
Topic
Weblog
Wiki Page
文字列照合
Document Actions
文字列照合問題
KMP 法
- text: ABBCX ... pat: ABBCB
- 5文字目で照合失敗
- 1文字ずらすと
- text: BCCX ... pat: A で失敗
- B は B であって A ではない
- 4 文字ずらして照合再開すればよい
パターンの中に同じパターンがあると
- pat の位置 5 で一致しなくなったら
- pat の位置 2 から照合再開
- next[j] に入れておく
ABCABA- next : [0, 0, 0, 1, 2]
プログラム
文字列照合の実際
- アルファベット（文字集合）が大きい
- 同じパターンが出てくることは少ない
- アルファベットが小さい例
- DNA : {A,T,G,C}
C言語ライブラリ
正規表現
- Regular Expression (regex, re)
- 形式言語理論
定義
- アルファベット A={a1,...,an} 上の正規表現とは
- 空記号列 ε は正規表現である
- ai（Aの任意の要素）は正規表現である
- X と Y が正規表現ならば、
- X|Y も正規表現である （どれかに一致）
- XY も正規表現である （連結）
- {X}* も正規表現である（繰り返し）
正規表現（計算機用）
- a ... a という文字に一致
- [abc] ... a または b, c の1文字に一致
- . (dot) ... 任意の１文字に一致
- * (asterisk) ... 直前の１文字の 0回以上の繰り返し
- ^ (caret) ... 先頭に一致
- $ (dollar) ... 末尾に一致
正規表現のアルゴリズム
- 有限オートマトン
- Automaton （自動人形・自動機械）
- 入力により「状態」が変わる（状態遷移）
ab という正規表現
プログラム例
- 単純に if で state 変数を制御
- ab.py
プログラム例（２）
- 状態遷移表を作り、それに従って state 変数を制御
状態＼文字 a b c 1 2 1 1 2 1 3 1 3 受理 - abtbl.py
- 状態と動作を別の表にしたりもする
別の例 a.*b
参考：（決定｜非決定）オートマトン
本日の問題
- a.*b の正規表現について状態遷移表を作りなさい
