diff options
author | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2003-01-31 06:48:54 +0000 |
---|---|---|
committer | matz <matz@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2003-01-31 06:48:54 +0000 |
commit | d18922065b186a88a8b37b19779a20a6eb1d9993 (patch) | |
tree | 7f617ab5cb7425dc95cb8af02d542b48584f4a25 | |
parent | 466d685a76b39695ac20cd9f55957e2e54b7636e (diff) | |
download | ruby-d18922065b186a88a8b37b19779a20a6eb1d9993.tar.gz |
* string.c (rb_str_index): search using Karp-Rabin algolithm.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@3429 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 4 | ||||
-rw-r--r-- | string.c | 26 |
2 files changed, 28 insertions, 2 deletions
@@ -1,3 +1,7 @@ +Fri Jan 31 14:16:59 2003 Yukihiro Matsumoto <matz@ruby-lang.org> + + * string.c (rb_str_index): search using Karp-Rabin algolithm. + Fri Jan 31 12:45:11 2003 Yukihiro Matsumoto <matz@ruby-lang.org> * variable.c (rb_obj_classname): new function. @@ -840,6 +840,7 @@ rb_str_index(str, sub, offset) { char *s, *e, *p; long len; + int d, hx, hy, i; if (offset < 0) { offset += RSTRING(str)->len; @@ -851,10 +852,31 @@ rb_str_index(str, sub, offset) len = RSTRING(sub)->len; if (len == 0) return offset; e = RSTRING(str)->ptr + RSTRING(str)->len - len + 1; + + /* seach using Karp-Rabin algolithm described in: + + EXACT STRING MATCHING ALGORITHMS + http://www-igm.univ-mlv.fr/~lecroq/string/index.html + */ + +#define KR_REHASH(a, b, h) ((((h) - (a)*d) << 1) + (b)) + + /* Preprocessing */ + /* computes d = 2^(m-1) with + the left-shift operator */ + for (d = i = 1; i < len; ++i) + d = (d<<1); + + for (hy = hx = i = 0; i < len; ++i) { + hx = ((hx<<1) + p[i]); + hy = ((hy<<1) + s[i]); + } + + /* Searching */ while (s < e) { - if (rb_memcmp(s, p, len) == 0) { + if (hx == hy && rb_memcmp(p, s, len) == 0) return (s-(RSTRING(str)->ptr)); - } + hy = KR_REHASH(*s, *(s+len), hy); s++; } return -1; |