Função em C ++ para encontrar se uma palavra for prefixo

Question

Digamos que eu tenha algumas palavras ab, aab, aa.

O AB não é um prefixo do AAB, mas AA é um prefixo da AAB, porque se eu apenas adicionar B no final do AA, ele se tornará AAB, o que não é possível com AB.

Então, existe alguma função em C ++ (STL) para que eu possa determinar duas palavras se um for prefixo para o outro?

Obrigado.

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

Observe que a verificação de comprimento não é a otimização prematura, é necessário atender à pré -condição da STD :: Equal.

Answer 2

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

ou que tal:

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

Esta resposta funciona com C e C ++ e não requer 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

Se você já depende do impulso, há 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;
}

Sempre que você encontrar std::string está sem um método de manipulação de cordas que você precisa, confira o Aumente os algoritmos de string biblioteca.

Answer 6

Use o find método de uma string. Verifique se o índice retorna está no início da string.

Answer 7

http://www.cplusplus.com/reference/string/string/ é um bom lugar para procurar coisas como essa. Reserve 10 minutos para se familiarizar com essas funções, porque a maioria delas é muito útil.

Você pode usar o Find para encontrar o texto em qualquer lugar da outra string, mas o find_first_of pode ser mais apropriado (e comparar com o sufixo). Caso contrário, para encontrar o sufixo, find_last_of seria apropriado.

Answer 8

A resposta real para o seu problema, eu acho, está usando uma árvore de prefixo. O algoritmo de respostas aceitas fará o trabalho, mas você teria que verificar sua palavra prefixo-para todas as outras palavras que são lineares no tempo. Faça isso por todas as palavras (diga que você quer obter todas as palavras que são prefixos para outras palavras) e você tem complexidade O (n^2) em suas mãos. A verificação simples se uma palavra é um prefixo para outro é linear sobre o comprimento da palavra.

O uso de uma árvore de prefixo responderá sua primeira pergunta no tempo logarítmico e a segunda - em linear. Verificar se uma palavra é um prefixo é apenas um passeio descendo da raiz até você encontrar a palavra na árvore e o último nó não é uma folha (o que significa que uma palavra mais longa que ela existe) - limitada pela altura da árvore. Atravessar a árvore, por outro lado, e escrever a palavra atual em cada etapa para a qual o último nó não é uma folha produziria uma lista de todas as palavras prefixos. A travessia da árvore é feita em tempo linear, pois você visitará cada nó apenas uma vez.

Answer 9

Se você apenas descobrir uma corda ou substring é prefixo de outra coisa que você pode simplesmente usar este FN

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

Se não existir, retorna um valor de lixo e se você está fazendo o mesmo para um não. de cordas e quero fazer de maneira rápida, você tem que usar o Trie.