文字列照合問題 #
文字列照合問題 (string-matching problem) とは
「与えられたパターン P が T に出現する正当なシフトをすべて見つける問題」
である。
ただし、この定義や、文字列照合問題では以下の表現を使うっぽい。
P, T とは #
- いずれも文字列(string) である
- P の文字数を m, T の文字数を n とし、P[1..l] を P の最初の l 文字の部分文字列とする
- つまり P = パターン、T = P を含むかもしれない文字列 のこと
パターン P が T のシフト s に出現する (occur with shift s) #
- 0 <= s ,= n-m かつ T[s+1..s+m] = P[1..m] であることを指す表現。
- つまり、「P と T の左端の文字を合わせて、s 文字だけ P を右に移動したら T の一部と一致する」ということ
- 例）P = “hello”, T = “abchello” だとするとき、「パターン P は T のシフト 3 に出現する」
valid shift, invalid shift #
- P と T の左端の文字を合わせて s だけ右に移動(shift)すると、P[1..m] と T[s+1..s+m] は一致する場合に、その shift を valid shift と呼ぶ
- 一致しない場合に、その shift を invalid shift と呼ぶ