Функция в c ++ для определения того, является ли слово префиксом

StackOverflow https://stackoverflow.com/questions/2482716

  •  21-09-2019
  •  | 
  •  

Вопрос

Допустим, у меня есть несколько слов AB, AAB, AA.

AB не является префиксом к AAB, но AA является префиксом к AAB, потому что, если я просто добавлю B в конце AA, это станет AAB, что невозможно с AB.

Итак, есть ли какая-нибудь функция в c ++ (STL), чтобы я мог определить из двух слов, является ли одно префиксом к другому?

Спасибо.

Это было полезно?

Решение 

template<class C, class T, class A>
bool starts_with(std::basic_string<C,T,A> const& haystack,
                 std::basic_string<C,T,A> const& needle)
{
  return needle.length() <= haystack.length() &&
    std::equal(needle.begin(), needle.end(), haystack.begin());
}

Обратите внимание, что проверка длины не является преждевременной оптимизацией, она необходима для выполнения предварительного условия std::equal .

Другие советы

std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

или о чем:

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;

std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);

Этот ответ работает с C и C ++ и не требует STL.

// test if string2 a prefix of string1
// inputs must be non NULL
// returns TRUE if string2 is a prefix, otherwise FALSE

int isAPrefix(const char *string1,
              const char *string2)
{
    return (strncmp(string1, string2, strlen(string2)) == 0);
}

Если вы уже зависите от Boost, есть boost::algorithm::starts_with.

int main()
{
    std::cout << boost::algorithm::starts_with("abba", "ab"); // true
    std::cout << boost::algorithm::starts_with("abba", "ba"); // false
    return 0;
}

Всякий раз, когда вы находите std::string не хватает нужного вам метода манипулирования строками, ознакомьтесь с Строковые алгоритмы повышения библиотека.

Используйте find метод строки.Проверьте, находится ли возвращаемый им индекс в начале строки.

http://www.cplusplus.com/reference/string/string/ это хорошее место, чтобы поискать подобные вещи.Потратьте 10 минут на то, чтобы ознакомиться с этими функциями, потому что большинство из них очень полезны.

Вы можете использовать find для поиска текста в любом месте другой строки, но find_first_of может быть более подходящим (и сравнивать с суффиксом).В противном случае, чтобы найти суффикс, было бы уместно использовать find_last_of .

Я думаю, что реальный ответ на вашу проблему - это использование дерева префиксов.Алгоритм принятых ответов выполнит эту работу, но вам придется проверить, соответствует ли ваш префикс любому другому слову в вашем наборе слов, который линейен по времени.Сделайте это для всех слов (скажем, вы хотите получить все слова, которые являются префиксами к другим словам), и у вас будет O (n ^ 2) сложности на руках.Простая проверка того, является ли одно слово префиксом к другому, линейна по длине слова.

Использование дерева префиксов даст ответ на ваш первый вопрос за логарифмическое время, а на второй - за линейное.Проверка того, является ли слово префиксом, - это просто прогулка вниз от корня вверх, пока вы не найдете слово в дереве, и последний узел не будет листом (что означает, что существует более длинное слово, расширяющее его), ограниченное высотой дерева.С другой стороны, при обходе дерева и записи текущего слова на каждом шаге, для которого последний узел не является листом, будет получен список всех слов-префиксов.Обход дерева выполняется за линейное время, так как вы посетите каждый узел только один раз.

Если вы просто обнаружите, что одна строка или подстрока является префиксом, отличным от u, вы можете просто использовать этот fn

 std::size_t found = str1.find(str2); //returns position of str2 in str1 (if found==0) than it is prefix else not.

Если он не существует, то он возвращает мусорное значение и если вы делаете то же самое для no.из строк и хотите сделать быстро, вы должны использовать TRIE.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top