#Pythonで学ぶアルゴリズム< 文字列探索の力任せ法 >
##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第27弾として文字列探索の力任せ法を扱う．
##文字列探索の力任せ法
前から順に一致する文字列を探すという非常に単純な方法．ここでは，検索対象を「テキスト」，見つけたい文字列を「パターン」と呼ぶこととする．例えば，'she sells sea shells'というテキストの中で，'sea'というパターンが最初に登場する位置を探すことを想定する．そのイメージ図を次に示す．
上図は少し省略して描いている．本当は，一致しなかったときには検索開始位置を１つ文字分ずつずらしていく．ここでは，イメージしやすいように，１文字目で不一致となる部分を省略している．上図からも分かるとおり，見つけ次第終了，見つけるまではひたすらずらしては探してという操作を繰り返す．文字通り，力任せ法である．
##実装
上の説明に従って，Pythonでの実装を行う．以下にソースコードとそのときの出力を示す．
#####ソースコード
"""
2021/02/01
@Yuya Shimizu
文字探索の力任せ法
"""
def search_string(text, pattern):
for i in range(len(text)):
match = True #patternと一致すると仮定
for j in range(len(pattern)):
#patternを順に1文字ずつ比較する
if text[i + j] != pattern[j]:
match = False #不一致
break #探索箇所を次に移行するため，これ以上の探索はしない
if match: #すべて一致した ⇒ 発見 ⇒ 探索終了
return i
if __name__ == '__main__':
TEXT = 'she sells sea shells'
PATTERN = 'sea'
where = search_string(TEXT, PATTERN)
print(f"{where}\nthat is, you can find {PATTERN} by running 'TEXT[{where}: {where}+len(PATTERN)]'")
#####出力
10
that is, you can find sea by running 'TEXT[10: 10+len(PATTERN)]'
探索の結果，テキストのにおけるパターンの開始位置を出力し，その結果からどのようにしてそのパターンをテキストにおいてアクセスできるかというのも出力として表示させてみた．実際にその指示に従って，print()などで表示させれば，パターンが得られることが確認できる．
##注意
テキストが今回のようなサイズであれば一瞬で処理は終了するが，長いテキストになると長時間かかることは原理から容易にわかる．
##感想
今回は非常に単純であったが，注意にもあるように長いテキストだと大変なようだ．しかしながら，このような探索をしたいときというのは長いテキストから何かを見つけたいときが多いような気がする．もう少し工夫して高速にした方法は次回学ぶため，非常に楽しみである．また，参考文献では，テキストとターゲットをlist()を使ってリスト化していたが，文字列のままでも大丈夫であった．ここには何か違いがあるのだろうか．また調べてみたい．
##参考文献
Pythonで始めるアルゴリズム入門 伝統的なアルゴリズムで学ぶ定石と計算量
増井 敏克 著 翔泳社