Функция в C++ для поиска префикса слова

Question

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

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

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

Благодарю.

Answer 1

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.

Answer 2

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

или как насчет:

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

Answer 3

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

Answer 4

Этот ответ работает с 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);
}

Answer 5

Если вы уже зависите от 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 не хватает необходимого вам метода манипуляции со строками, посмотрите библиотеку Boost String Algorithms.

Answer 6

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

Answer 7

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

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

Answer 8

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

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

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

Answer 9

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

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