when search a modle string in a paper,we can use KMP method,but if a modle string like "ababababababc" or "abcabcabcabcd",its nextfunction can't work effectively beacuse when we work out next( 13),it should be 3 directly instead of indirectly,who have method more effectively
Posted on 2003-06-16 23:34:50 by feizhongshvi
A frequency count of letters could be maintained to ensure least likely letters are tested first. Good only for large alphabets.

Example: find "abcd" in "abcabcabcabcd"

abcabcabcabcd

{letter} = {count}
d=1
a=4
b=4
c=4

Therefor, test "d" position first.

abc[u]a[/u]bcabcabcd

abcd

abcabc[u]a[/u]bcabcd
abcd

abcabcabc[u]a[/u]bcd
abcd

abcabcabc[u]abcd[/u]
[u]abcd[/u]
In this case KMP does this already, no? Since "a" <> "d" position is advanced to first character (from last position) that can match "a". This happens three times and finally found string.


Look at even first character missing - still good find, but more comparisons:
bcd[u]b[/u]cdbcdabcd

abcd

bcd[u]bcd[/u]bcdabcd
a[u]bcd[/u]

bcdbcdbcd[u]a[/u]bcd
abcd

bcdbcdbcd[u]abcd[/u]
[u]abcd[/u]



note: this is algorithm question not MASM32 package specific.
Posted on 2003-06-17 00:12:37 by bitRAKE
you reply fit only three letters repeated,but l want to know if we don't know how many letters are repeated,what shall we do
Posted on 2003-06-17 04:51:28 by feizhongshvi
It should work with more letters repeated:

http://www-igm.univ-mlv.fr/~lecroq/string/node8.html

There are many posts on the board, too.

Search: "KMP string search"
Posted on 2003-06-17 07:45:25 by bitRAKE