在流中搜索字符串的有效方法

对于部分搜索，我对Knuth Morris
Pratt算法做了一些更改。由于实际比较位置始终小于或等于下一个位置，因此不需要额外的存储空间。带有Makefile的代码也可以在github上找到，并且用Haxe编写，可以同时针对多种编程语言，包括Java。

我还写了一篇相关文章：在流中搜索子字符串：Haxe中对Knuth-Morris-
Pratt算法的略微修改。文章提到了Jakarta RegExp，它现已退休并在Apache
Attic中休息。RE类中的Jakarta Regexp库“
match
”方法使用CharacterIterator作为参数。

class StreamOrientedKnuthMorrisPratt {    var m: Int;    var i: Int;    var ss:    var table: Array<Int>;    public function new(ss: String) {        this.ss = ss;        this.buildTable(this.ss);    }    public function begin() : Void {        this.m = 0;        this.i = 0;    }    public function partialSearch(s: String) : Int {        var offset = this.m + this.i;        while(this.m + this.i - offset < s.length) { if(this.ss.substr(this.i, 1) == s.substr(this.m + this.i - offset,1)) {     if(this.i == this.ss.length - 1) {         return this.m;     }     this.i += 1; } else {     this.m += this.i - this.table[this.i];     if(this.table[this.i] > -1)         this.i = this.table[this.i];     else         this.i = 0; }        }        return -1;    }    private function buildTable(ss: String) : Void {        var pos = 2;        var cnd = 0;        this.table = new Array<Int>();        if(ss.length > 2) this.table.insert(ss.length, 0);        else this.table.insert(2, 0);        this.table[0] = -1;        this.table[1] = 0;        while(pos < ss.length) { if(ss.substr(pos-1,1) == ss.substr(cnd, 1)) {     cnd += 1;     this.table[pos] = cnd;     pos += 1; } else if(cnd > 0) {     cnd = this.table[cnd]; } else {     this.table[pos] = 0;     pos += 1; }        }    }    public static function main() {        var KMP = new StreamOrientedKnuthMorrisPratt("aa");        KMP.begin();        trace(KMP.partialSearch("ccaabb"));        KMP.begin();        trace(KMP.partialSearch("ccarbb"));        trace(KMP.partialSearch("fgaabb"));    }}