我有两个字符串，长度相同。我必须检查它们是否可以表示为 XYZ 和 XZY，其中 Y 和 Z 不为空。
我的解决方案是“吃掉”两个字符串的相同首字母，然后找到最长的公共子字符串进行休息。然后检查第一个字符串的其余部分和第二个字符串的其余部分（没有 LCS）是否相等。问题是，我听说过 O(N) 内存复杂度算法，但我发现的只是 O(MN)。我的记忆力有限，所以这对我很重要。
第二种解决方案是使用 "(.*)(.+)(.+)\1\3\2" 正则表达式，但这是非常糟糕的解决方案。
有人有其他想法吗？
3 回答
2
可能是这样的：
bool test(string& s1, string& s2)
{
if (s1.size() != s2.size())
{
return false;
}
for (size_t i = 1; i < s1.size()-2; i++)
{
if (s1.substr(0,i) != s2.substr(0,i)) return false;
for (size_t j = 1; j < s1.size()-i; j++)
{
string x1 =s1.substr(i,j);
string x2 =s1.substr(i+j);
string y1 = s2.substr(i, s1.size()-i - j);
string y2 = s2.substr(s1.size()-j);
if ((x1==y2) && (x2==y1))
{
cout << "X: " << s1.substr(0,i) << endl;
cout << "Y Z: " << x1 << " " << x2 << endl;
cout << "Z Y: "<< y1 << " " << y2 << endl << endl;
return true;
}
}
}
return false;
}
int main()
{
string s1 {"abcbd"};
string s2 {"abdbc"};
if (test(s1, s2))
{
cout << "OK" << endl;
}
else
{
cout << "NOT OK" << endl;
}
return 0;
}
如果内存对您来说是一个真正的大问题，您可以通过逐个字符比较来避免子字符串。例如：
if (s1.substr(0,i) != s2.substr(0,i)) return false;
可以替换为
for (size_t z = 0; z < i; z++)
{
if (s1[z] != s2[z]) return false;
}
同样，您可以通过引入两个类似的 for 循环来避免字符串 x1、x2、y1 和 y2，在其中您可以逐个字符地进行比较。
代码将更难阅读和理解，但它会使用更少的内存。
bool test(string& s1, string& s2)
{
size_t N = s1.size();
if (N != s2.size())
{
// s1 and s2 must have same length
return false;
}
// i is length of X
for (size_t i = 1; i < s1.size()-2; i++)
{
// Check that X of length i exists in both s1 and s2
for (size_t k = 0; k < i; k++)
{
if (s1[k] != s2[k]) return false;
}
// Now check for YZ in s1[i..N-1] and ZY in s2[i..N-1]
//
// j is length of Y
// N-i-j is length of Z
for (size_t j = 1; j < N-i; j++)
{
// Is s1[i..i+j-1] == s2[N-j..N-1]?
bool b1 = true;
for (size_t k = 0; k < j; k++)
{
if (s1[i+k] != s2[N-j+k]) b1=false;
}
// Is s1[i+j..N-1] == s2[i..N-j-1]?
bool b2 = true;
for (size_t k = 0; k < (N-i-j); k++)
{
if (s1[i+j+k] != s2[i+k]) b2=false;
}
if (b1 && b2)
{
// Success!
// For debug the value of i and j
// can be used to output the substrings
// using for-loops
cout << "X=";
for (size_t k = 0; k < i; k++)
{
cout << s1[k];
}
cout << endl;
cout << "Y=";
for (size_t k = i; k < (i+j); k++)
{
cout << s1[k];
}
cout << endl;
cout << "Z=";
for (size_t k = (i+j); k < N; k++)
{
cout << s1[k];
}
cout << endl;
return true;
}
}
}
return false;
}
int main()
{
string s1 {"abcbd"};
string s2 {"abdbc"};
if (test(s1, s2))
{
cout << "OK" << endl;
}
else
{
cout << "NOT OK" << endl;
}
return 0;
}
于 2015-06-22T20:21:31.837 回答
1
首先，停止复制东西：
template<class T>
struct array_view {
T* b = 0;
T* e = 0;
T* begin()const{return b;}
T* end()const{return e;}
// defaults:
array_view()=default;
array_view(array_view const&)=default;
array_view& operator=(array_view const&)=default;
~array_view()=default;
array_view( T* s, size_t n ):array_view(s, s+n){}
array_view( T* s, T* f ):b(s),e(f){}
using mutable_T = typename std::remove_const<T>::type;
template<size_t N>
array_view( T(&arr)[N] ):array_view(arr, N){}
template<size_t N>
array_view( std::array<T,N>&arr ):array_view(arr.data(), N){}
template<size_t N>
array_view( std::array<mutable_T,N>const&arr ):array_view(arr.data(), N){}
// similar for std::vector:
template<class...Ts>
array_view( std::basic_string<mutable_T, Ts...> const& src):
array_view(src.data(), src.size())
{}
template<class...Ts>
array_view( std::basic_string<T, Ts...>& src):
array_view(
src.empty()?
array_view():
array_view(std::addressof(src[0]),src.size())
)
{}
T& back() const { return *std::prev(end()); }
T& front() const { return *begin(); }
size_t size() const { return end()-begin(); }
bool empty() const { return begin()==end(); }
// slicing functions:
array_view front( size_t n ) const {
if (size() <= n) return *this;
return {begin(), n};
}
array_view back( size_t n ) const {
if (size() <= n) return *this;
return {end()-n, n};
}
array_view trim_front( size_t n ) const {
return back( size()-n );
}
array_view trim_back( size_t n ) const {
return front( size()-n );
}
array_view sub( size_t start, size_t len ) const {
if (start >= size()) return {};
len = (std::min)( size()-start, len );
return {begin()+start, len};
}
// comparisons:
friend bool operator==( array_view lhs, array_view rhs ) {
if (lhs.size()!=rhs.size()) return false;
return std::equal( lhs.begin(), lhs.end(), rhs.begin() );
}
friend bool operator!=( array_view lhs, array_view rhs ) {
return !(lhs==rhs);
}
friend bool operator<( array_view lhs, array_view rhs ) {
return std::lexicographical_compare(
lhs.begin(), lhs.end(),
rhs.begin(), rhs.end()
);
}
friend bool operator>( array_view lhs, array_view rhs ) {
return rhs<lhs;
}
friend bool operator<=( array_view lhs, array_view rhs ) {
return !(lhs>rhs);
}
friend bool operator>=( array_view lhs, array_view rhs ) {
return !(lhs<rhs);
}
};
anarray_view是一个没有拥有的范围。它不支持 char 特征，但我不太在意。
using string_view = array_view<const char>;
size_t common_prefix( string_view lhs, string_view rhs ) {
auto itl = lhs.begin();
auto itr = rhs.begin();
while (itl != lhs.end() && itr != rhs.end()) {
if (*itl != *itr) break;
++itl; ++itr;
}
return itl-lhs.begin();
}
lhs给了我们and的最长公共前缀rhs。
现在我们要做的就是快速有效地识别YZvs。ZY
bool is_yz_zy( string_view lhs, string_view rhs ) {
if (lhs.size() < 2) return false;
if (lhs.size() != rhs.size()) return false;
for (size_t i = 1; i < lhs.size(); ++i) {
if (lhs.front(i)==rhs.back(i)) {
if (lhs.trim_front(i) == rhs.trim_back(i)) {
return true;
}
}
}
return false;
}
并缝合：
bool is_xyz_xzy( string_view lhs, string_view rhs ) {
size_t max_x = common_prefix(lhs, rhs);
for (size_t i = 0; i <= max_x; ++i) {
if (is_yz_zy( lhs.trim_front(i), rhs.trim_front(i) ))
return true;
}
return false;
}
使用 O(1) 内存。
优化时间。
进行异或扫描。现在唯一x可能的长度是那些在该索引处异或扫描相等的长度，并且整个字符串的异或扫描相等。
类似地，对于 yz zy 检测，索引 i 处的左 xor 扫描必须等于索引长度处的右 xor 扫描 - i xor 右 xor 扫描长度为 i 的长度为 y。
具有仍然友好属性的更强大的哈希将使病理情况不那么明显，但异或扫描应该有很大帮助。
异或扫描是所有先前字符的异或。这可以在字符串中就地完成，将每个字符替换为自身的 xor 和所有先前的字符。该操作很容易反转，并且需要线性时间。
字符串比较需要一点小心，但您只需将每个扫描条目与前一次扫描进行异或即可获得原始字符。
于 2015-06-22T21:33:38.277 回答
0
未经证实，深思。
- 反转第二个字符串并附加到第一个字符串，例如 XYZY'Z'X'。（或相反）
- 找到可能的最长 X == X'（此处可能需要一些算法讨论），其中 size(X) <= len(XYZY'Z'X')/2
- 从size(X)迭代到0。在每次迭代中，去掉两端的X，使得字符串为YZY'Z'，并通过对中间字符串进行分区来验证YZ == Y'Z'，如果验证通过则返回True .
- 迭代后，返回false。
于 2015-06-22T20:17:36.053 回答