Mastering Algorithms With Perlperlは写経でいまいち理解度があやしいため、pythonでBoyer-Moore法を。パターンとの不一致の場合には何文字スキップできるか、一致した場合に何文字スキップできるかのテーブルを最初に作っておいて、スキップ幅の大きいほうでスキップしながらパターンマッチを進めていく。
def boyer_moore_bad_character (P): m = len(P) bc = [m] * 256 j = m for char in list(P): bc[ord(char)] = j - 1 j -= 1 return m, bc def boyer_moore_good_suffix (m,P): j = m + 1 gs = [0] * j k = [0] * j k[m] = j for i in reversed(range(1,j)): while j <= m and P[i-1] != P[j-1]: if gs[j] == 0: gs[j] = j - i j = k[j] j -= 1 k[i-1] = j kn = k[0] for j in range(m+1): if gs[j] == 0: gs[j] = kn if j == kn: kn = k[kn] gs.pop(0) return gs def boyer_moore (T,P): (m,bc) = boyer_moore_bad_character(P) gs = boyer_moore_good_suffix(m,P) (i, last_i, first_j) = (0, len(T)-m, m-1) for i in range(last_i+1): j = first_j while j >= 0 and T[i+j] == P[j]: j -= 1 if j < 0: return i else: bcn = bc[ord(T[i+j])] - m + j + 1 gsn = gs[j] i += bcn if bcn > gsn else gsn return -1 if __name__ == '__main__': print boyer_moore("perlpypythonruby","python")
- pythonはコードの見通しがよいですな
- perlと違ってsubstrとかやらなくてもいいので見通しがよい
- perlのshiftがpop(0)なのがあれ。先頭をpopするってのが。
- perlだと$a[5]=5とやれるけど、pythonはそれ以前の要素が自動的ににundefで埋まらない
for文でカウンタ変数使いたかったのでrangeをつかったけどPython流はどうやるのがよろしいんだろうか、、、カウンタ変数減算するのにfor i in reversed(range(1,j))だしな。