Простой алгоритм поиска по шаблону в C ++ - PullRequest
Новая
       9

Простой алгоритм поиска по шаблону в C ++

2 голосов
/ 16 ноября 2011

У меня есть задание, в котором я должен создать шаблон поиска, включающий подстановочный знак «?».Мы еще не рассмотрели ничего, кроме циклов и свойств строковых библиотек, поэтому мой учитель не хочет, чтобы я использовал массивы или что-то, что мы не рассмотрели.

Моя задача - создать алгоритм для специального символа '?'.Есть ли у вас идеи, как я могу интегрировать его в свою программу, не используя более продвинутые трюки?Все, что я пробовал, либо полностью неверно, либо содержит некоторые ошибки.

Программа должна запросить у пользователя ввод исходной строки, а затем запросить другой ввод для строки поиска, который может включать '?'в этом.Например:

Исходная строка: великолепная Строка поиска:? R? O

Соответствующая строка была найдена в индексе: 2 Соответствующая строка: orio

Ответы [ 6 ]

2 голосов
/ 16 ноября 2011

Я чувствовал себя плохо только для намека на возврат и рекурсию в комментарии. Вот объяснение:

Стратегия:

Сосредоточьтесь на жетонах между wilcards (подстановочные знаки - это не то, что должно совпадать).

  • извлечь первый токен из шаблона
  • успешный выход из игры без (более) токенов
  • для каждого совпадения токена на входе
    • сопоставить остаток шаблона с остатком ввода
    • если нет успешного совпадения, произойдет сбой, иначе будет сделано

Существует рекурсия (рекурсивное сопоставление совпадения класса остатка (....)).

Существует возврат (если рекурсивное совпадение не удается, мы пробуем следующий субматч токена)

Образец ( см. https://ideone.com/yApYp)

Только с использованием циклов и интерфейса std::string (ну и iostreams для отображения тестового вывода):) 

#include <iostream>
#include <string>

typedef std::string::const_iterator It;

/*
 * Extract sequences of non-wildcard characters from pattern range
 */
std::string extract_token(It &s, It e) // [s,e) is (sub)pattern
{
    It wcard;
    for (wcard=s; wcard!=e; ++wcard)
        if ('?' == *wcard) break;

    std::string token(s,wcard);

    for (s=wcard; s!=e; ++s)
        if ('?' != *s) break; // treat '??' as '?' in pattern

    return token;
}

/*
 * Match a (sub)pattern against a (sub)input
 *
 * (See "Strategy" above)
 */
bool match(It patb, It pate, const std::string& input)
{
    while (patb != pate)
    {
        // get next token from pattern, advancing patb
        std::string token = extract_token(patb, pate); // updates patb

        if (!token.empty()) // could happen if pattern begins/ends with redundant '?'
        {
            size_t submatch = input.find(token);  // first submatch please

            while (std::string::npos != submatch)  // while we have a submatch
            {
                if (match(patb, pate, input.substr(token.size())))
                    return true; // match completed successfully

                // look for later potential submatches (*backtrack*)
                submatch = input.find(token, submatch+1);
            }
            return false; // required token not found
        }
    }
    return true; // no (remaining) pattern, always match
}

bool match(const std::string& pattern, const std::string& input)
{
    // just relay to overload more suited for recursion
    return match(pattern.begin(), pattern.end(), input); 
}

//////////////////////
// TEST PROGRAM

void test(const std::string& pattern, const std::string& input)
{
    std::cout << std::boolalpha;
    std::cout << "match(\"" << pattern << "\", \"" << input << "\") => " 
              << match(pattern, input) << std::endl;
}

int main()
{
    // matches
    test("?????",               "");
    test("?????",               "?????");
    test("",                    "");
    test("",                    "glorious");
    test("?r?o",                "glorious");
    test("some?words?exist",    "some silly words should, most definitely, be existing");
    test("some??words?exist?",  "some silly words should, most definitely, be existing");

    // failing matches
    test("_",                   "");
    test("_",                   "glorious");
    test("_",                   "glorious");
    test("glorious",            "glo?ious");
    test("?some??words?exist?", "bogus");
}
2 голосов
/ 16 ноября 2011

Возможно, вам лучше всего создать две функции. Один проверяет, соответствует ли шаблон строке в некоторой заданной позиции, а другой - использует первую функцию для проверки всех позиций входной строки.

Функция, которая проверяет совпадение шаблона, будет зацикливаться на всех символах в шаблоне, и для каждого из этих символов проверяется, равен ли он ? или идентичен символу в соответствующей позиции входной строки. 1004 *

0 голосов
/ 14 мая 2014

На прошлой неделе я начал перемещать свои частные и публичные репозитории из bitbucket, и я вспомнил об этом.

Открытая реализация подстановочных знаков C ++.Нативные C / C ++ & .NET

Теперь он отделен от нового «песочницы» новым проектом из моей песочницы в виде легких, быстрых и мощных символов подстановки в дополнение к движку медленного регулярного выражения и т. Д. 

enum MetaSymbols
{
    MS_ANY      = _T('*'), // {0, ~}
    MS_SPLIT    = _T('|'), // str1 or str2 or ...
    MS_ONE      = _T('?'), // {0, 1}, ??? - {0, 3}, ...
    MS_BEGIN    = _T('^'), // [str... or [str1... |[str2...
    MS_END      = _T('$'), // ...str] or ...str1]| ...str2]
    MS_MORE     = _T('+'), // {1, ~}
    MS_SINGLE   = _T('#'), // {1}
    MS_ANYSP    = _T('>'), // as [^/]*  //TODO: >\>/ i.e. '>' + {symbol}
};

Какреализовать собственный и т. д. Смотрите здесь:

Впрочем, это также возможно и для пользователей .NET через Conari engine.

В общем, смотрите реализацию «как это работает» или используйте «как есть» (лицензия MIT) 

#include "regXwildAPI.h"

using namespace net::r_eg::regXwild;

...
if(searchEssC(_T("regXwild"), _T("reg?wild"), true)) {
    // ...
}

searchEss(data, _T("^main*is ok$"));
searchEss(data, _T("^new*pro?ection"));
searchEss(data, _T("pro*system"));
searchEss(data, _T("sys###s"));
searchEss(data, _T("new+7+system"));
searchEss(data, _T("some project|open*and*star|system"));
...

Таким образом, я обновил свойстарый ответ.Наслаждайтесь.

0 голосов
/ 17 января 2013

См. Мой ответ здесь , который также должен быть достаточно быстрым для большинства целей (он максимально избегает выделения кучи, и в основном это недетерминированный конечный автомат).

0 голосов
/ 18 ноября 2011

Вот функция, которую я придумал. Наконец я нашел способ, используя свои ограниченные знания. Это работает, но, вероятно, производительность действительно плохая.

Спасибо за вашу помощь, они вдохновили меня, хотя я не могу использовать их напрямую из-за передовых методов. 

void wildcard(string source, string search)
{
    unsigned int j = 0, i = 0, z = 0;
    string s1 = "", search2 = search;
    //Starting with a null string and adding found parts to it

    /*************************IF IT STARTS WITH QUESTION MARK*************************/

    if(search.find('?') == 0)
    {
        for(; search.at(z) == '?'; z++)
            //loop make search string start without question marks.
        {
            search2 = search.substr(z + 1, search.length());
        }

        for(; j <= source.length()-search2.length(); ++j)
            //application of Brute Force Search Algoritm for this case.
        {
            while(i < search2.length() && (source.at(z+i+j) == search2.at(i) || search2.at(i) == '?'))
            {
                s1 = s1 + source.at(z+j+i);
                i++;
            }
        }

        if(s1.length() == search2.length())
            //showing results for this case.
        {
            cout << "The matched string was found at index: " << source.find(s1) - z << endl;
            cout << "The matched string is: " << source.substr((source.find(s1)-z), search.length()) << endl << endl;
        }
        else
        {
            cout << "The search string could not found in the source string." << endl << endl;
        }
    }

    /********************IF IT DOES NOT START WITH QUESTION MARK**********************/

    else
        //If it doesnot start with ?, use normal test.
    {
        for(; j <= source.length()-search.length(); ++j)
            //application of Brute Force Search Algoritm for this case.
        {
            while(i < search.length() && (source.at(i+j) == search.at(i) || search.at(i) == '?'))
            {
                s1 = s1 + source.at(j+i);
                i++;
            }
        }

        if(s1.length() == search.length())
            //results
        {
            cout << "The matched string was found at index: " << source.find(s1) << endl;
            cout << "The matched string is: " << s1 << endl << endl;
        }
        else
        {
            cout << "The search string could not found in the source string." << endl << endl;
        }
    }
}
0 голосов
/ 16 ноября 2011

Возможно, думайте о подстановочном знаке как соответствующем каждому символу, пока не дойдете до следующего символа или конца строки. Таким образом, алгоритм будет: 

if NextCharToMatch is ? then
  get the next search char
  loop until the input equals the new char to match
...