Function in c++ for finding if a word is prefix

Let say i have some words AB, AAB, AA.

AB is not a prefix to AAB but AA is a prefix to AAB because if i just add B at the end of AA it will become AAB, which is not possible with AB.

So, is there any function in c++ (STL) so t开发者_如何学Gohat i can determine of two words if one is prefix to the another ?

Thanks.

---

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

Note that the length check is not premature optimization, it is required to meet std::equal's precondition.

---

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

or what about:

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

---

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

---

This answer works with C and C++ and doesn't require 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);
}

---

If you're already dependent on Boost, there's 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;
}

Whenever you find std::string is lacking a string manipulation method you need, check out the Boost String Algorithms library.

---

Use the find method of a string. Check if the index it returns is at the beginning of the string.

---

http://www.cplusplus.com/reference/string/string/ is a good place to look through for stuff like this. Take 10 minutes to familiarise yourself with these functions, because most of them are very useful.

You can use find to find the text anywhere in the other string, but find_first_of could be more appropriate (and compare against the suffix). Otherwise to find the suffix, find_last_of would be appropriate.

---

The real answer to your problem, i think, is using a prefix tree. The accepted answers algorithm will do the job, but you would have to check your prefix-wouldbe word to every other in your word set which is linear in time. Do that for all the words (say you wanna get all the words that are prefixes to other words) and you have O(n^2) complexity on your hands. The simple check whether a word is a prefix to another is linear on the word's length.

Using a prefix tree will answer your first question in logarithmic time and the second - in linear. Checking if a word is a prefix is just a stroll down from the root up until you find the word in the tree and the last node is not a leaf (meaning a longer word extending it exists) - limited by the height of the tree. Traversing the tree, on the other hand, and writing down the current word on each step for which the last node is not a leaf would yield a list of all prefix words. The tree traversal is done in linear time as you will visit each node only once.

---

If you just find out one string or substring is prefix of other than u can simply use this fn

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

If it doesn't exists than It returns a garbage value and If U doing the same for a no. of strings and wanna to do in fast way you have to use TRIE.