Функция в 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

Если вы уже зависите от 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 5

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

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

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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

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