CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Nov 2017
    Posts
    2

    boyer moore algorithm

    i am to Write a program to use Boyer Moore Algorithm to find the pattern in the string. my program can define string as “BARD LOVED BANANAS” . i need to ask user to input pattern to search. i need to display two tables. 1for good suufix shift of pattern and another to display the shift value for each step. If not match, display a message “Unsuccessful Search”. If match, display the index.
    im kind of stuck with my code. any help will be appreciated

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: boyer moore algorithm

    m kind of stuck with my code
    If you post what you have, we'll be able to advise.
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    Join Date
    Nov 2017
    Posts
    2

    Re: boyer moore algorithm

    Code:
    #include<iostream>
    #include<string>
    #include<algorithm>
    
    using namespace std;
    
    int BoyerSearch(int m,int n,string str, string pattern,int shft[]);
    
    int main()
    {
    
         string str="BARD LOVED BANANAS";// source string
         cout<<"BARD LOVED BANANAS"<<endl;
         string pattern= ""; //pattern to match
         cout<<"p=";
         cin>>pattern;
    
         int n=str.length();//length of the source string
    
         int m=pattern.length();//length of the pattern string
    
         string alphabet="";
    
         int shft[100];//shift table
    
         bool flag=false;
         
         //find the alpahbets
    
         for(int i=0;i<str.length();i++)
         {
              flag=false;
              for(int j=0;j<alphabet.length();j++)
              {
                  if(str.at(i)==alphabet.at(j))
                       flag=true;
              }
    
              if(flag!=true)
                  alphabet=alphabet+str.at(i);
         }
    
         std::sort(alphabet.begin(),alphabet.end());
    
         cout<<"alphbets in the given source string: "<<alphabet<<" "<<endl;
    
         //create shift table for the charcters occured in the pattern
    
         for(int i=0;i<100;i++)
         {
              shft[i]=m;
         }
    
         for(int j=0;j<m-1;j++)
         {
              int t=pattern.at(j);
    
              shft[t]=m-1-j;
         }
    
         //print shift table
    
         cout<<"Shift table: "<<endl;
    
         for(int j=0;j<m;j++)
         {
              cout<<pattern.at(j)<<" ";
         }
    
         cout<<endl<<"---------------"<<endl;
    
         for(int j=0;j<m;j++)
         {
              cout<<shft[pattern.at(j)]<<" ";
         }
    
         cout<<endl;
    
         //call for search
    
         int k=BoyerSearch(m,n,str,pattern,shft);
    
         if (k!=0)
              cout<<"Pattern found at="<<k<<endl;
         else
              cout<<"Not found"<<endl;
    
         system("pause");
    
         return 0;
    }
    
    int BoyerSearch(int m,int n,string str, string pattern,int shft[])
    {
         int k=0;
    
         while(k<=n-m)
         {
              int i=m-1;
    
              while(i>=0 && str.at(k+i)==pattern.at(i))
              {
                  i--;
              }
    
              if (i<0)
              {
                  return k;
              }
    
              k=k+shft[str.at(k+m-1)];
         }
    
         return 0;//returns 0, if the pattern is not found
    
    }
    //that is all i have so far
    Last edited by 2kaud; November 15th, 2017 at 11:37 AM. Reason: Added code tags

  4. #4
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: boyer moore algorithm

    [When posting code, please use code tags so that the code is readable. Go Advanced, select the formatted code and click '#'.]
    All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!

    C++23 Compiler: Microsoft VS2022 (17.6.5)

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured