Funzione in C ++ per la ricerca di se una parola è prefisso

Question

Let dire che ho qualche parola AB, AAB, AA.

AB non è un prefisso di AAB ma AA è un prefisso di AAB perché se gli appena aggiungo B alla fine di AA diventerà AAB, che non è possibile con AB.

Quindi, c'è una funzione in C ++ (STL) in modo che posso determinare di due parole, se uno è prefisso per l'altro?

Grazie.

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

Si noti che il controllo di lunghezza non è l'ottimizzazione prematura, che è necessario per soddisfare std :: precondizione di parità.

Answer 2

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

o che dire:

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

Questa risposta funziona con C e C ++ e non richiede 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 sei già dipendente da Boost, c'è 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;
}

Ogni volta che trovate std::string manca un metodo di manipolazione delle stringhe è necessario, controllare il Boost biblioteca String Algoritmi .

Answer 6

Utilizzare il metodo find di una stringa. Controllare se l'indice restituisce è all'inizio della stringa.

Answer 7

http://www.cplusplus.com/reference/string/string/ è un buon posto per guardare attraverso per cose come questa. Prendere 10 minuti per familiarizzare con queste funzioni, perché la maggior parte di loro sono molto utili.

È possibile utilizzare Trova per trovare il testo in qualsiasi altra stringa, ma find_first_of potrebbe essere più appropriata (e confrontare con il suffisso). In caso contrario, per trovare il suffisso, find_last_of sarebbe opportuno.

Answer 8

La vera risposta al vostro problema, credo, sta usando un albero prefisso. L'algoritmo di risposte accettato farà il lavoro, ma si dovrà controllare la parola prefisso-wouldbe ad ogni altro nel set parola che è lineare nel tempo. Farlo per tutte le parole (ad esempio si desidera ottenere tutte le parole che sono prefissi ad altre parole) e si ha O (n ^ 2) la complessità sulle vostre mani. Il semplice controllo se una parola è un prefisso ad un altro è lineare dalla lunghezza della parola.

Utilizzo di un albero prefisso sarà rispondere alla tua prima domanda in tempo logaritmico e la seconda - in lineare. Controllare se una parola è un prefisso è solo una passeggiata lungo dalla radice fino a trovare la parola nella struttura e l'ultimo nodo non è una foglia (che significa una parola più lungo che si estende esiste) - limitato per l'altezza dell'albero. Attraversare l'albero, d'altra parte, e scrivere la parola corrente su ogni scatto il cui ultimo nodo non è una foglia produrrebbe un elenco di tutte le parole prefissi. L'attraversamento albero è fatto in tempo lineare, come vi permetterà di visitare ogni nodo una sola volta.

Answer 9

Se hai appena scoperto una stringa o sottostringa è prefisso diverso da u può semplicemente utilizzare questo fn

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

In caso contrario esiste quello che restituisce un valore di immondizia e se u fare lo stesso per un no. di stringhe e voglia di fare in modo veloce è necessario utilizzare TRIE.