[comp.lang.pascal] Hashing....

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