String.prototype.indexOf가 상당히 빠른 것 같아요.

이런 Suffix Aray를 만들어 보았습니다(산열을 사용했지만).
suffixarray.js

function SuffixArray(str) {
  var
  i, c, sa = {};
  this.str = str;

  for (i = 0; c = str.charAt(i); i++) {
    (sa[c] || (sa[c] = [])).push(i);
  }
  this.sa = sa;
}

SuffixArray.prototype.search = function (word, start) {
  if (!word) return 0;
  start = start || 0;

  var
  i,
  is = this.sa[word.charAt(0)], l = (is || []).length;

  for (i = 0; i < l; i++) {
    if (is[i] >= start && this.str.substr(is[i], word.length) === word) return is[i];
  }
  return -1;
}

Suffix Aray라고 하면 보통 2진법 검색이 있는데 2진법 검색보다 해시가 더 빠를 것 같아서 해시로 써봤어요.(JavaScript의 객체를 해싱이라고 할 수 있습니까?)
그리고 String.prototype.indexOf와 String.prototype.search(정규 표시판 indexOf)는 각각 속도를 비교했다.
나는 jsPerf라는 것을 알고 그곳에서 해 보았다.
여기서 ↓.
String.prototype.indexOf vs String.prototype.search(RegExp) vs my SuffixArray · jsPerf
결과:

이런 느낌이야.오페라 17이 뭔지 느껴지지만 안에 크롬이 80% 정도 들어있어서 크롬일 거예요.
이것은 길수록 빠른 것 같아서 indexOf가 가장 빠르다.그리고 Suffix Arry보다 배 이상 빨라요.
응, indexOf 선형 탐색은 아니지...
그나저나 Firefox의 결과도 크게 다르지 않다(8배의 시간이 걸렸지만)