文字列の中から効率良くキーワードを探し出せ：コーディングに役立つ！アルゴリズムの基本（7）（1/4 ページ）

プログラマたるものアルゴリズムとデータ構造は知っていて当然の知識です。しかし、教科書的な知識しか知らなくて、実践的なプログラミングに役立てることができるでしょうか（編集部）

» 2009年02月04日 00時00分公開

[山下寛人，オイシックス株式会社]

　前回「Firebugで探索アルゴリズムを見ていこう」では、数値の集合の中から特定の数値を探索しました。今回は文字列の中から検索ワードを探索してみましょう。

　UNIXのコマンドならgrep、Javaなどのプログラムなら文字列のindexOfメソッドなどに相当する処理です。

力任せ法

　それでは例によって最もベタなアルゴリズムの紹介から始めましょう。

　文字列の中に検索ワードがあるかどうか調べます。文字列の先頭から1文字ずつ検索ワードと比較していきます。不一致があったら文字列の2文字目から1文字ずつ検索ワードと比較します。全部一致したらそこで処理終了です。

　サンプルプログラムを見てみましょう。

<html>
<head>
<script type="text/javascript">
function getStringById(id) {
  var element = document.getElementById(id);
  var str = element.value;
  if (str == undefined) {
    str = element.innerHTML;
  }
  return (str == undefined) ? "" : str;
}
</script>
</head>
<body>
<div id="area1">
大事な人と毎日食べるものだから、
手をかけなくても、おいしいものを
国内最大規模の食品販売サイトＯｉｓｉｘ(おいしっくす)。
安心はあたりまえ、おいしく・忙しくてもつづけやすく・カラダにいい食材を毎週、
旬の野菜やフルーツ・パン・牛乳・お肉など2400商品の中から、お客様のご希望に
あわせてお好きな時間に、全国にお届けしています。
</div><br>
<input id="search" type="text" value="しく・忙しく">
<script type="text/javascript">
String.prototype.find = function(str) {
  var text_idx_len = this.length - str.length + 1;
  for(var text_idx = 0; text_idx < text_idx_len; text_idx++) {
    var isFound = true;
    for(var i = 0; i < str.length; i++) {
      if(str.charAt(i) != this.charAt(text_idx + i)) {
        isFound = false;
        break;
      }
    }
    if(isFound) { return text_idx; }
  }
 
  return null;
}
 
function findTextArea(text_id, search_id) {
  var text = getStringById(text_id);
  var search = getStringById(search_id);
  alert(text.find(search));
}
</script>
<input type="button" onClick="findTextArea('area1','search');" value="find">
<!-- 末尾1 -->
 
</body>
</html>

　プログラムを解説します。検索対象の文章はオイシックスのWebサイトから引用しました。

4～11行目

HTML中の指定のidの中の文字列を取得する関数です。

15～22行目

検索対象になる文字列です。好きな文章に変えてみるのもよいでしょう。

25～39行目

力任せ法のプログラムです。

27行目

検索対象の文字列を順に1文字ずつ調べます。

29行目

検索ワード1文字ごとにループして調べていきます。

30～33行目