3

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 that i can determine of two words if one is prefix to the another ?

Thanks.

VaioIsBorn
  • 7,683
  • 9
  • 31
  • 28
  • I think you really mean the C++ stdlib ("standard library") rather than the STL (which is commonly misunderstood). –  Mar 20 '10 at 11:20
  • @Roger I think "sdlib" is equally likely to be misunderstood. I've never hears the standard library referred to like that, and of course "stdlib.h" is one of the C standard headers. –  Mar 20 '10 at 12:28
  • @Neil: I am honestly very surprised you have not heard it before. You're not wrong in that it could be misunderstood, but it at least doesn't mean something different from what he intended. For example, your excellent answer below uses nothing from the STL and wouldn't even be applicable if he really meant STL. –  Mar 20 '10 at 13:00
  • What you're looking for is strncmp. – D Drmmr Mar 18 '18 at 21:36

9 Answers9

9
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.

  • 3
    +1 This solution doesn't have to create a second substring and doesn't spend time looking for a match anywhere other that the start of the string. – CB Bailey Mar 20 '10 at 11:02
5
std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

or what about:

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;
3
std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);
Alexander Gessler
  • 45,603
  • 7
  • 82
  • 122
2

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);
}
Stephen Kellett
  • 3,078
  • 1
  • 22
  • 25
2

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.

Emile Cormier
  • 28,391
  • 15
  • 94
  • 122
  • But of course in this case, std::string doesn't lack that method (unless you insist on having a method with an explicit name), so you don't. –  Mar 20 '10 at 16:26
1

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

Eli Bendersky
  • 263,248
  • 89
  • 350
  • 412
1

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.

Salami
  • 1,048
  • 1
  • 10
  • 17
0

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.

pnt
  • 1,916
  • 1
  • 20
  • 29
0

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.

Ravi
  • 11
  • 4