2 Replies - 769 Views - Last Post: 31 October 2013 - 09:41 AM Rate Topic: -----

#1 LaVeritas   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 14
  • Joined: 10-February 11

Why doesn't my Horspool implementation work for some strings?

Posted 31 October 2013 - 03:49 AM

I implemented the algorithm according to a tutorial. It works fine for most strings. But some strings do produce errors or wrong results.

//Returns a dictionary => "bad match table"
Dictionary<char,int> berechneTabelle(string suchString)
{
    //Length of the pattern
    int m = suchString.Length;


    bool replacedEntry = false;
    Dictionary<char, int> alphabet = new Dictionary<char,int>();
    alphabet.Add('*',m);

    for(int i = 0;i<suchString.Length-1;i++)
    {
        if(alphabet.ContainsKey(suchString[i]))
        {
            alphabet.Remove(suchString[i]);
            alphabet.Add(suchString[i], m - i - 1);
            replacedEntry = true;
        }

        if(!replacedEntry)
        {
            alphabet.Add(suchString[i], m - i - 1);
        }                
    }            

    return alphabet;
}

//Finds the occurence of P in T
int findeP(Dictionary<char,int> alphabet,string T,string P) 
{
    int m = P.Length;
    int position = 0;
    bool foundPinT = false;

    while (!foundPinT)
    {                
        string subString = T.Substring(position,m );
        bool matched = true;

        for (int i = m - 1; i >= 0;i--)
        {                    

            if(subString[i] == P[i] && matched)
            {
                matched = true;
            }

            if (i == 0 && matched && subString[i] == P[i] && matched)
            {
                foundPinT = true;
                break;
            }

            if (!(subString[i] == P[i]))
            {


                if (alphabet.FirstOrDefault(x => x.Key == subString[i]).Value != 0)
                {
                    position += alphabet.FirstOrDefault(x => x.Key == subString[i]).Value;
                    matched = false;
                    break;
                }
                else 
                {
                    position += m;
                    subString = T.Substring(position, m);
                    matched = true;
                    break;
                }    
            }
        }
    }
    return position;
}


This works fine:

Pattern: truth
Text: We hold these truths to be self-evident

This doesn't work:

Pattern: tahah
Text: abtahah

Is this beacuse I didn't implement it correctly or is this a algorithm related problem?

Is This A Good Question/Topic? 0
  • +

Replies To: Why doesn't my Horspool implementation work for some strings?

#2 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6216
  • View blog
  • Posts: 21,452
  • Joined: 05-May 12

Re: Why doesn't my Horspool implementation work for some strings?

Posted 31 October 2013 - 06:10 AM

Did you try stepping through the code with a debugger to see where it starts failing to find matches?

Being able to program means not only being able to translate algorithms into code, but also being able to debug the code to see if it is working correctly.
Was This Post Helpful? 1
  • +
  • -

#3 Momerath   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1021
  • View blog
  • Posts: 2,463
  • Joined: 04-October 09

Re: Why doesn't my Horspool implementation work for some strings?

Posted 31 October 2013 - 09:41 AM

View PostLaVeritas, on 31 October 2013 - 03:49 AM, said:

Is this beacuse I didn't implement it correctly or is this a algorithm related problem?

The algorithm was first published in 1980, do you think they'd still be teaching it if it had problems?

I've not had a chance to watch the video, but I can see in your program that you do some odd things (and since I haven't see the video, I don't know if it is you or the instructor :)/>)

Some weirdness:
Line 14-24: You check if it contains then set a flag if it doesn't so you can do some other code. This is an if/else. You don't need a flag at all.

Lines 60,62: You use a dictionary (with an O(1) lookup) then force it to use LINQ (O(n) lookup) to find an entry?
This does the same thing but operates in O(1):
alphabet.Contains(subString[i]) ? alphabet[subString[i]] : 0;


Lines 64,71: You have an if/else with a break in each condition. Move the break out of the if/else since you always want to do it.

Line 10: No idea why you put this.

I'll look over the algorithm itself when I can, and watch the video :)/>

P.S. Line 12 has an error. You either need to do < length or <= length-1. What you have now skips the very last character of the string.
P.P.S. Lines 45-48: You set matched = true but only if matched == true. Looks like a bug to me :)/>

This post has been edited by Momerath: 31 October 2013 - 10:09 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1