athos@apple.com (Rick Eames) (09/25/89)
I am a relatively new programmer and I am searching for a good algorithim for finding one pattern in a source string. A friend of mine says that hashing it is a good way. Having figured out what hashing is...does any one have a good hash function for finding a string inside of another string? Thanks! Rick Eames
bkottman@wright.EDU (Brett Kottmann) (09/26/89)
in article <4337@internal.Apple.COM>, athos@apple.com (Rick Eames) says: > > I am a relatively new programmer and I am searching for a good algorithim > for finding one pattern in a source string. A friend of mine says that > hashing it is a good way. Having figured out what hashing is...does any > one have a good hash function for finding a string inside of another > string? > Look in "Software components with Ada" by Grady Booch for a great alogrithm. (Page 530..551) It's in Ada type code but it's close enough to Pascal for use.
aqm@mace.cc.purdue.edu (Steve Weinrich) (09/26/89)
athos@apple.com (Rick Eames) writes: >hashing it is a good way. Having figured out what hashing is...does any >one have a good hash function for finding a string inside of another >string? Well Rick, there are several ways to go about finding a string within a string. If all you will be doing with each string is trying to find it within another string, then I'm not sure a full fledged hashing function would be worth your while. Nothing like using an elephant gun to kill an ant. What you might consider doing instead is a simple (yes, I said it! simple! ugggg!) sequential search. But do it in a reasonable fashion. Something similar to the code below might be what you are looking for: root = string you are search THROUGH find = string you are looking FOR function In_String(root : TyString, find : TyString): boolean; Rindex, Findex, temp_index : integer; found, test : boolean; begin found := false; test := true; Rindex := 1; Findex := 1; temp_index := 1; while (Rindex <= (StringLength + 1)) and (not found) do begin if root[Rindex] = find[1] then begin Findex := 1; temp_index := Rindex; test := true; found := false; while test and not(found) do begin test = (root[temp_index] = find[Findex]) do temp_index := temp_index + 1; Findex := Findex + 1; if Findex > StringLength then found := true; end; end else begin Rindex := Rindex + 1; end; {while} InString := found; end; {function} Good luck. This was written on the fly, probably forgot some error checking, but you get the idea. -- Steve Weinrich - Purdue University - Unix Group Support E-Mail: aqm@cc.purdue.edu