Función en C ++ para encontrar si una palabra es el prefijo

Question

Vamos a decir que tengo algunas palabras AB, AAB, AA.

AB no es un prefijo a AAB, pero AA es un prefijo a AAB porque si acabo de añadir B al final de AA se convertirá en AAB, que no es posible con AB.

Entonces, ¿hay ninguna función en C ++ (STL) de modo que pueda determinar de dos palabras si uno es prefijo al otro?

Gracias.

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

Tenga en cuenta que la comprobación de longitud no es la optimización prematura, se requiere para cumplir con std :: condición de igualdad.

Answer 2

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

o lo que acerca de:

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 respuesta trabaja con C y C ++ y no requiere 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

Si usted está ya en función de Boost, hay 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;
}

Cada vez que encuentre std::string se carece de un método de manipulación de cadenas que necesita, echa un vistazo a la Boost biblioteca de cadenas Algoritmos .

Answer 6

Utilice el método find de una cadena. Compruebe si el índice es que vuelve al principio de la cadena.

Answer 7

http://www.cplusplus.com/reference/string/string/ es un buen lugar para buscar a través de cosas como esta. Tomar 10 minutos para familiarizarse con estas funciones, porque la mayoría de ellos son muy útiles.

Puede utilizar Buscar para buscar el texto en cualquier lugar de la otra cadena, pero find_first_of podría ser más apropiado (y comparar contra el sufijo). De lo contrario, para encontrar el sufijo, find_last_of sería apropiado.

Answer 8

La verdadera respuesta a su problema, creo, está utilizando un árbol de prefijo. El algoritmo respuestas aceptado hará el trabajo, pero se tendría que revisar su palabra de prefijo-wouldbe a todos los demás en su conjunto palabra que es lineal en el tiempo. Hacer que todas las palabras (decir que desea obtener todas las palabras que son prefijos a otras palabras) y tiene complejidad O (n ^ 2) en sus manos. El simple comprobación de si una palabra es un prefijo a otro es lineal en la longitud de la palabra.

El uso de un árbol de prefijo responderá a su primera pregunta en el tiempo logarítmica y el segundo - en el lineal. Comprobación de si una palabra es un prefijo que es sólo un paseo hacia abajo desde la raíz hasta que encuentre la palabra en el árbol y el último nodo no es una hoja (es decir, una palabra más larga que se extiende existe) - limitado por la altura del árbol. Recorrer el árbol, por otro lado, y anotando la palabra actual en cada paso para el que el último nodo no es una hoja produciría una lista de todas las palabras de prefijo. El recorrido del árbol se realiza en tiempo lineal a medida que se visita cada nodo sólo una vez.

Answer 9

Si usted acaba de descubrir una cadena o subcadena es el prefijo de otra que u puede simplemente utilizar este fn

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

Si no existe lo que devuelve un valor de basura Si U y hacer lo mismo para un no. de cuerdas y quiere hacer de la manera rápida usted tiene que utilizar TRIE.