sm
BAN USER///////////////////////////////////////////////////////////////////////////////
// @file FindLongestLargerSubString.cxx
// @compile g++ -Wall -o FindLongestLargerSubString FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
#include <string.h>
#include <assert.h>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
using namespace std;
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// @function FindLongestLargerSubString
///////////////////////////////////////////////////////////////////////////////
// @decription Given a string S, print the longest substring P such that P > S
// lexicographically. You may assume that such substring exists.
///////////////////////////////////////////////////////////////////////////////
// @param pS const char* const - the input string [IN]
//
// @param rIdx reference to an unsigned int - upon return this will have the
// the index of the larger substring, unless such a substring does not exist,
// in which case it will be set to UINT_MAX; one consequence of this is
// the length of the input string, excluding the terminating character, must
// be no larger than UINT_MAX - 0x2
///////////////////////////////////////////////////////////////////////////////
// @return bool true if found, false otherwise
///////////////////////////////////////////////////////////////////////////////
// @performance O(n) in number of characters in pS
///////////////////////////////////////////////////////////////////////////////
bool FindLongestLargerSubString(const char* const pS, unsigned int& rIdx)
{
///////////////////////////////////////////////////////////////////////////
assert(pS);
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
bool bRet = false;
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
unsigned int nLen = strlen(pS);
///////////////////////////////////////////////////////////////////////////
// We are assured that such a substring, P, exists. Adopting the convention
// a string is also one of its substrings (akin to every set being its
// own subset), if P exists, then P != S. Why? Well, we are given that
// P > S (lexicographically), and S !> S. To satisfy this, S must be at
// least two characters long. Assert it.
//
// Note: even if caller does not abide by the contract of passing a
// string to us that has at least a lexicographically larger substring,
// we will assert if length of string is less than two characters, but
// also detect that no such substring exist.
///////////////////////////////////////////////////////////////////////////
if (nLen < 0x2) {
///////////////////////////////////////////////////////////////////////
cout << "\n\tBroken contract - input length < 2. Bailing!\n\n"
<< flush;
///////////////////////////////////////////////////////////////////////
assert(nLen > 0x1);
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
rIdx = UINT_MAX;
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// Remember the beginning character.
///////////////////////////////////////////////////////////////////////////
char beginChar = pS[0x0];
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// We wish to remember the position, if it exists, of a character
// downstream that matches begin.
///////////////////////////////////////////////////////////////////////////
int matchBeginPos = 0x0;
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// Start from the second character in the string (we are assured that there
// is a second character - see comments above.
///////////////////////////////////////////////////////////////////////////
for (int idx = 0x1; idx < nLen; idx++) {
///////////////////////////////////////////////////////////////////////
if (matchBeginPos == 0x0) {
///////////////////////////////////////////////////////////////////
if (pS[idx] > beginChar) {
///////////////////////////////////////////////////////////////
// We are done
///////////////////////////////////////////////////////////////
rIdx = idx;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
} else if (pS[idx] == beginChar) {
///////////////////////////////////////////////////////////////
matchBeginPos = idx;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
// Nothing to do.
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
// Have already seen a character that matches beginChar
///////////////////////////////////////////////////////////////////
if (pS[idx] > pS[idx - matchBeginPos]) {
///////////////////////////////////////////////////////////////
// We are done. Have found it.
///////////////////////////////////////////////////////////////
rIdx = matchBeginPos;
///////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
// If caller hasn't abided by contract of having at least one substring
// P > S lexicographically, then we indicate it with the return value.
///////////////////////////////////////////////////////////////////////////
if (rIdx < UINT_MAX) {
///////////////////////////////////////////////////////////////////////
bRet = true;
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
return bRet;
///////////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////////
// @function main
///////////////////////////////////////////////////////////////////////////////
// @decription the entry-point into our program
///////////////////////////////////////////////////////////////////////////////
// @param argc int, the argument count
//
// @param argv pointer to an array of strings, the arguments to the program,
// one for each argc
///////////////////////////////////////////////////////////////////////////////
// @return int 0x0 if succeeded, !0x0 otherwise
///////////////////////////////////////////////////////////////////////////////
#define UNUSED(X)
///////////////////////////////////////////////////////////////////////////////
int
main(int UNUSED(argc), char** UNUSED(argv))
{
///////////////////////////////////////////////////////////////////////////
std::string terminate = ".";
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
std::string s;
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
unsigned int idx = 0x0;
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
while (true) {
///////////////////////////////////////////////////////////////////////
cout << "Enter a string ('.' to end): " << flush;
///////////////////////////////////////////////////////////////////////
cin >> s;
///////////////////////////////////////////////////////////////////////
if (s != terminate) {
///////////////////////////////////////////////////////////////////
if (FindLongestLargerSubString(s.c_str(), idx)) {
///////////////////////////////////////////////////////////////
cout << "\n\t" << (s.c_str()) + idx << endl << flush;
///////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////
cout << "\n\t"
<< "No P > S found. Broken contract!\n"
<< flush;
///////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////
} else {
///////////////////////////////////////////////////////////////////
break;
///////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////
}
///////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////
return 0x0;
///////////////////////////////////////////////////////////////////////////
}
Normalized input string by converting to lowercase:
- sm March 19, 2016