Error with running BruteForce algorithmn?

Question

I'm taking a users input like so:

algo_type "pattern" filename

ex.

bf "inging" input_file.txt

As of now I separate the users input into three different variables, one for the algo_type, one for the pattern I'm looking for, and one for the filename. Once I get the pattern and filename I'm trying to take the pattern into the Bruteforce algo and search each line and print the position that pattern occurs in the line of the .txt file. Right now though every time I enter the input into the algo it returns -1 meaning the BruteForce isn't running? What exactly am I doing wrong here?

int BruteForce(const string& line, const string& pattern){
    int n , m;
    n = line.length();
    m = pattern.length();

    for(int  i = 0 ; i < n - m ; i++){

            int j = 0;

            while( j < m  && line[i + j] == pattern[j]){
            j = j+1;

            if( j == m){
                    return i;

                    }
            }        
    }
    return -1; 
 }

  int main(){

    string text, algo_type , pattern , fname, line;
    getline(cin ,text);
    istringstream  iss(text);

    if(iss >>  algo_type  >>  pattern  >> fname){
            cout <<  algo_type  <<  pattern << fname << "'\n'";
    }

    int i = 0;
    ifstream ifs;
    ifs.open(fname.c_str());
    while(getline(ifs, line) && fname != ""){
            if( algo_type == "bf"){
                    cout << "Line " << i++ << ":" << BruteForce(line,pattern) << endl;

            }
    }
    return 0;
  }

Why did you edit your question with the fix from my answer? Are you saying the question remains, even with the edit? It's unclear now — sehe, Sep 08 '13 at 18:46
I put return -1; in the proper location. Still though my Brute Force algo is not functional. I'm thinking there is a problem with how I am reading the .txt file? — user2757849, Sep 08 '13 at 18:48
Is there a reason why you're not using `std::string::find` or `std::find`? — sehe, Sep 08 '13 at 18:51
I added using namespace std; Apologies for not making that clear. — user2757849, Sep 08 '13 at 18:54
That wasn't the point. You're not using the obvious library features. The `std::` letters are immaterial here — sehe, Sep 08 '13 at 18:58

sehe · Accepted Answer · 2013-09-08T19:35:40.350

2

I suppose you wanted return -1 at the end of BruteForce, rather then at the end of the first iteration.

Also, the first loop condition needs to have <= instead of <, or matches ending in the very position won't be found.

Here's a complete, fixed version: EDIT as per the edit, list multiple matches within lines:

#include <string>

using namespace std;

int BruteForce(const string& line, size_t start, const string& pattern) {
    const size_t n = line.length();
    const size_t m = pattern.length();

    if (n<m) return -1;

    for(size_t i = start; i <= (n - m); i++) {
        for(size_t j=0; j < m  && (line[i + j] == pattern[j]); ++j) {
            if(j == m-1) {
                return i;
            }
        }
    }
    return -1;
}

#include <iostream>
#include <fstream>
#include <sstream>

int main() {
    string text, algo_type, pattern, fname, line;
    getline(cin ,text);
    istringstream iss(text);
    if(iss >>  algo_type  >>  pattern  >> fname) {
        cout << " " << algo_type  << " " << pattern <<  " " <<fname << "\n";
    }

    int i = 1;
    ifstream ifs;
    ifs.open(fname.c_str());
    while(getline(ifs, line) && fname != "") {
        if(algo_type == "bf") {
            int pos = -1;

            while (-1 != (pos = BruteForce(line, pos+1, pattern)))
                cout << "Line " << i << ":" << pos << " " << line << endl;
        }
        i++;
    }
    return 0;
}

See it Live on Coliru: http://coliru.stacked-crooked.com/a/f1a7693d7d3bd7c5

I've tested it with

./test <<< "bf iss /etc/dictionaries-common/words" | grep Miss

Which printed

Line 10241:1 Miss
Line 10242:1 Mississauga
Line 10242:4 Mississauga
Line 10243:1 Mississippi
Line 10243:4 Mississippi
Line 10244:1 Mississippi's
Line 10244:4 Mississippi's
Line 10245:1 Mississippian
Line 10245:4 Mississippian
Line 10246:1 Mississippian's
Line 10246:4 Mississippian's
Line 10247:1 Mississippians
Line 10247:4 Mississippians
Line 10248:1 Missouri
Line 10249:1 Missouri's
Line 10250:1 Missourian
Line 10251:1 Missourian's
Line 10252:1 Missourians
Line 10253:1 Missy
Line 10254:1 Missy's

edited Sep 08 '13 at 19:35

answered Sep 08 '13 at 18:43

sehe

374,641
47
450
633

Thank you I will definitely add that functionality. – user2757849 Sep 08 '13 at 18:46
@user2757849 I think I've found the culprit, though. You will want to mind your `consts` and _signed/unsigned_ comparisons :/ – sehe Sep 08 '13 at 19:09
Right ok, so your algo and mine have the same exact output regarding finding the first occurrence of the pattern, the problem now is that other occurrences happen in the same line. So the algo finds the first occurrence and then moves to the next line without finding other occurrences of the pattern within the line. – user2757849 Sep 08 '13 at 19:21
@user2757849 As far as I'm concerned, that's perfectly fine. Also, your algorithm as originally written did **not** find the same solutions (because that's what I fixed the first loop's condition for). – sehe Sep 08 '13 at 19:23
For example I'm reading a text file and Line 1: consists of "Reaching a fever pitch and it's bring me out the dark" if I search "ing" the Brute Force finds the first position of the pattern string which is 5 but there is also another occurrence at position 34 but the Algo does not read that far once it finds the first occurrence it moves to the next line. If that makes any sense? – user2757849 Sep 08 '13 at 19:25
Ok that make sense, do you have any hints on how I should go about looking for more than one occurrence of the pattern in the .txt line? Is it a matter of introducing some while loop that only stops till it reaches the end of the line and keeps running the for loop looking for the pattern? – user2757849 Sep 08 '13 at 19:27
If you now want to list _all_ matches, that's fine, but you didn't ask for that initially. However, see, amended version: http://coliru.stacked-crooked.com/a/f1a7693d7d3bd7c5 (searches for `const` in it's own source, lists multiple matches per line) ***(also edited post + example)*** – sehe Sep 08 '13 at 19:32
Hmm..still not the functionality I'm looking for unfortunately. Instead of printing out the line I just want to print out the occurrence of where the pattern occurs everywhere in that line. Right now it prints the first occurrence then the actual line, which is interesting but unneeded. – user2757849 Sep 08 '13 at 19:54
@user2757849 Well, I can't help you. If you can't even figure out how to change that, you deserve to read a good book on programming, not more spoonfeeding. Head over here: [the-definitive-c++-book-guide-and-list](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) – sehe Sep 08 '13 at 19:57
2

Your more than right I am completely new to C++ and could do with some study I appreciate the assistance though it's been extremely helpful with making me understand and debug my code, much appreciated, sorry for any frustration. – user2757849 Sep 08 '13 at 20:03

Error with running BruteForce algorithmn?

1 Answers1