Ошибка при запуске алгоритма BruteForce?

Я принимаю пользовательский вклад, например, так:

algo_type "pattern" filename

ех.

bf "inging" input_file.txt

На данный момент я разделяю пользовательский ввод на три разные переменные, одну для algo_type, одну для шаблона, который я ищу, и одну для имени файла. Как только я получаю шаблон и имя файла, я пытаюсь взять шаблон в алгоритме Bruteforce, обыскивать каждую строку и печатать позицию, в которой шаблон находится в строке файла .txt. Прямо сейчас, хотя каждый раз, когда я вводю ввод в алгоритм, он возвращает -1, что означает, что BruteForce не работает? Что именно я здесь делаю не так?

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;
}

1

Решение

Я полагаю, вы хотели return -1 в конце BruteForce, а не в конце первой итерации.

Кроме того, условие первого цикла должно иметь <= вместо <или совпадения, заканчивающиеся в самой позиции, не будут найдены.

Вот полная исправленная версия: РЕДАКТИРОВАТЬ согласно редактированию перечислите несколько совпадений в строках:

#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;
}

Посмотрите это в прямом эфире на Coliru: http://coliru.stacked-crooked.com/a/f1a7693d7d3bd7c5

Я проверил это с

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

Который напечатан

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
2

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector