Changes between Initial Version and Version 1 of GB11921/2013-05-20


Ignore:
Timestamp:
05/20/2013 03:01:46 PM (11 years ago)
Author:
chris
Comment:

—

Legend:

Unmodified
Added
Removed
Modified

  • GB11921/2013-05-20

    v1 v1  
     1== データ構造とアルゴリズム 第5週 ==
     2
     3=== 文字列照合 ===
     4
     5表記法の定義
     6
     7文字列 text[1..n]
     8第i番目の文字 text[1]
     9text[i..j」
     10i==jのときはtext[i]
     11i>jのときはNULL
     12
     13text[1..n]があって、そのなかにpattern[1..m]があったら
     14
     15
     16単純照合法
     17
     18一致したら文字列とパターンの両方とも1文字右に進む
     19一致しなかったらpat[1]から1文字ずつ照合
     20
     21KMP法
     22
     23まくらパターンにしたがって見逃しを避けつつ、text上をなるべく大幅にpatternを右シフトさせることにより、単純法よりもはるかに高速な文字列検索処理が可能