文字列検索アルゴリズムの実装

Question

文字列内で部分文字列が使用された回数をカウントする単純な方法を使用して、文字列検索アルゴリズムを実装しました。私はjavascriptとpythonで実装しました。 （トップコーダーから）

アルゴリズム：

function brute_force(text[], pattern[]) 
{ 
    // let n be the size of the text and m the size of the 
    // pattern 
    count = 0 
    for(i = 0; i < n; i++) { 
    for(j = 0; j < m && i + j < n; j++) 
     if(text[i + j] != pattern[j]) break; 
     // mismatch found, break the inner loop 
    if(j == m) // match found 
     count+=1 
    return count 
    } 
} 

Javascriptの実装：

a = "Rainbow"; 
b = "Rain"; 
count = 0; 
function findSubStr(Str, SubStr){ 
    for (i = 0; i<a.length; i++){ 
     //document.write(i, '<br/>'); 
     for (j = 0; j < b.length; j++) 
      //document.write('i = ',i, '<br/>'); 
      //document.write(j, '<br/>'); 
      if(a[i + j] != b[j]) break; 
      document.write('j = ', j, '<br/>') 
      //document.write('i = ',i, '<br/>'); 
    if (j == b.length) 
     count+=1; 
    } 
    return count; 
} 
document.write("Count is ",findSubStr(a,b), '<br/>'); 

Python実装：

a = "Rainbow" 
b = "Rain" 
def SubStrInStr(Str, SubStr): 
    count = 0 
    for i in range(len(Str)): 
     for j in range(len(SubStr)): 
      print j 
      if (a[i + j] != b[j]): 
       break 
     if (j+1 == len(SubStr)): 
      count+=1 
    return count 
print(SubStrInStr(a, b)) 

今、私の質問は、実装ラインのためであるならば（j == b.length） ：それはjavascriptではうまく動作しますが、Pythonではvalに1を加える必要がありますまたはbの長さから1を引いたものである。なぜこれが起こっているのか分かりません。

Answer 1

for x in range(4) 

PythonのJavascriptとは異なり、forループはリスト内のすべての要素に使用されます。 xがかかる最後の値がリストの最後の要素である[0、1、2、3] 3

for(x = 0; x < 4; x++) 

はJavaScriptで、xは4の値を取ると、ループが終了するある< 4条件Xためもはや適用することはできません。最後の値xは4になります。

Answer 2

コードが同一ではないため、この混乱が生じています。 for (j = 0; j < b.length; j++)を実行するとjの最終値はb.length（bがaの部分文字列の場合）ですが、Pythonの場合は少し異なります。 range(len("1234"))を実行すると[0, 1, 2, 3]になるので、forはforeachのようになります。jは配列の最後の値を格納しています。このため、追加する必要があります。私は十分に明確であることを願っています。そうでない場合は、詳細をお尋ねください。

Answer 3

私はあなたのpythonの実装にいくつかの問題があることがわかります。 b = "raiy"を設定すると、関数は1を誤って返します。エッジ条件が誤っている可能性があります。 これらの2つの条件文は同じレベルになければなりません。

a = "Rainbow" 
b = "Rain" 
def SubStrInStr(Str, SubStr): 
    count = 0 
    for i in range(len(Str)): 
     for j in range(len(SubStr)): 
      # print (j) 
      if (a[i + j] != b[j]): 
       break 
      if (j+1 == len(SubStr)): 
       count+=1 
return count 
print(SubStrInStr(a, b))here