2009/02/06

文字列検索

文字列検索 - ときどきの雑記帖 i戦士篇

KMPとかBM ってマルチバイト文字とか幅広文字に使うの面倒だよねえ。

• BMはナイーブに書くと文字集合と同じ大きさのテーブルが必要になっちゃうけど、 utf-8文字列ならオクテット列に対して直接使えるからテーブルエントリは256で済む。
• KMPのリスタートベクタは文字集合の大きさとは関係無く検索文字列の長さで決まるから wide charでもutf-8なmultibyte charでもさして問題ない。

というわけで、mb1 : utf-8のように文字境界を誤ることのないmultibyte encoding、 mb2 : euc-jpのようにランダムアクセスで文字境界が確定しないmultibyte encoding、 とすると、こんなふうに理解してる：

Tag: Programming