ananthd
BAN USER<pre lang="c++" line="1" title="CodeMonkey3691" class="run-this">// RemoveAdjacentDuplicates.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <string>
#include <cassert>
typedef std::basic_string<char> string;
/*
RemoveAdjacentDuplicates: string, string -> string
Given two strings s1 & s2, this function returns a composite of s1 & s2;
If there is a trailing sub-string of s1 and a leading sub-string of s2 which are common,
Returns a concatenation of the prefix of s1, followed by the common substring, followed by the suffix of s2;
i.e if s1 = s1' + s' and if s2 = s' + s2' then the result is s1' + s' + s2'
If there is nothing in common, then s' becomes the empty string and the result will be a concatenation of the two strings.
*/
string
RemoveAdjacentDuplicates(string const& s1, string const& s2)
{
// Handle edge cases of one or both inputs being empty;
if (s1.empty()) return s2;
if (s2.empty()) return s1;
//Both strings must be non-empty if we got here;
assert(!s1.empty() && !s2.empty());
//find the last character of s1 anywhere in s2;
size_t m = s1.size();
//index into the current character of interest in s1;
string::size_type i = m - 1;
//index into the current character of interest in s2;
string::size_type pos = s2.find_last_of(s1[i]);
string s(s1); //return value initialized must atleast have s1;
string::size_type k = pos; //Offset just before the suffix that must be concatenated with s1;
if (pos != string::npos) {
assert(s1[i] == s2[pos]);
while (s1[i] == s2[pos] && i > 0 && pos > 0) { //make sure we don't run off s1 or s2;
--i; --pos;
}
assert(i >= 0 && pos >= 0);
if (pos > 0) { //Ran out of s1 but not s2, therefore no common sub-sequence;
k = string::npos;
}
}
s.append(s2.substr(k + 1));
return s;
}
int _tmain(int argc, _TCHAR* argv[])
{
struct {
const char* const s1;
const char* const s2;
} testBed[] = {
{ "", "" }, { "a", ""}, { "", "b"}, { "aa", ""}, { "", "bb"}, {"aaa", ""}, {"", "bbb"}, {"aa", "a"},
{"ab", "ba"}, {"ab", "ab"}, {"abc", "bcd"}, {"abcd", "bcde"},
{"Hello how is everyone", "everyone is good?"}, {"Hello how is everyone", "is everyone good?"},
{"Hello how is everyone", "Hi, is everyone"}, {"Totally", "Unrelated"},
};
for (int i = 0; i != sizeof(testBed)/sizeof(testBed[0]); ++i) {
string s(RemoveAdjacentDuplicates(testBed[i].s1, testBed[i].s2));
printf("s1 '%s' s2 '%s' result '%s'\n", testBed[i].s1, testBed[i].s2, s.c_str());
}
return 0;
}
</pre><pre title="CodeMonkey3691" input="yes">
// RemoveAdjacentDuplicates.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include <string>
#include <cassert>
typedef std::basic_string<char> string;
/*
RemoveAdjacentDuplicates: string, string -> string
Given two strings s1 & s2, this function returns a composite of s1 & s2;
If there is a trailing sub-string of s1 and a leading sub-string of s2 which are common,
Returns a concatenation of the prefix of s1, followed by the common substring, followed by the suffix of s2;
i.e if s1 = s1' + s' and if s2 = s' + s2' then the result is s1' + s' + s2'
If there is nothing in common, then s' becomes the empty string and the result will be a concatenation of the two strings.
*/
string
RemoveAdjacentDuplicates(string const& s1, string const& s2)
{
// Handle edge cases of one or both inputs being empty;
if (s1.empty()) return s2;
if (s2.empty()) return s1;
//Both strings must be non-empty if we got here;
assert(!s1.empty() && !s2.empty());
//find the last character of s1 anywhere in s2;
size_t m = s1.size();
//index into the current character of interest in s1;
string::size_type i = m - 1;
//index into the current character of interest in s2;
string::size_type pos = s2.find_last_of(s1[i]);
string s(s1); //return value initialized must atleast have s1;
string::size_type k = pos; //Offset just before the suffix that must be concatenated with s1;
if (pos != string::npos) {
assert(s1[i] == s2[pos]);
while (s1[i] == s2[pos] && i > 0 && pos > 0) { //make sure we don't run off s1 or s2;
--i; --pos;
}
assert(i >= 0 && pos >= 0);
if (pos > 0) { //Ran out of s1 but not s2, therefore no common sub-sequence;
k = string::npos;
}
}
s.append(s2.substr(k + 1));
return s;
}
</pre>
- ananthd November 21, 2010
Order matters in my solution. If s1 has a trailer in common with a header in s2, then it will return only the sequence of unique components.
- ananthd November 21, 2010