两个字符串 XYZ 和 XZY

Question

我有两个长度相同的字符串。我还要检查它们是否可以表示为 XYZ 和 XZY，其中 Y 和 Z 不为空。

我的解决办法是'eat'两个字符串的首字母相同，然后求最长公共子串。然后检查第一个字符串的其余部分和第二个字符串的其余部分（没有 LCS）是否相等。问题是，我听说过 O(N) 的内存复杂度算法，但我发现的只是 O(MN)。我的记忆力有限，所以这对我来说很重要。

第二种解决方案是使用“(.*)(.+)(.+)”正则表达式，但这是非常糟糕的解决方案。

还有人有其他想法吗？

Answer 1

未验证，深思。

反转第二个字符串并附加到第一个字符串，例如XYZY'Z'X'。（或反过来）
找到最长的 X == X'（此处可能需要一些算法讨论），其中 size(X) <= len(XYZY'Z'X')/2
从 size(X) 迭代到 0。在每次迭代中，从两端删除 X，使字符串为 YZY'Z'，并通过以下方式验证 YZ == Y'Z' 在中间划分字符串，return 如果验证为真。
迭代后，return false.

Answer 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;
}

Answer 3

首先，停止复制东西：

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

一个array_view是一个没有拥有的范围。它不支持字符特征，但我不在乎。

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 和 rhs 的最长公共前缀。

现在我们所要做的就是快速有效地识别 YZ 与 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) 内存。

live example

优化时间。

进行异或扫描。现在 x 唯一可能的长度是那些使异或扫描在该索引处相等的长度，和整个字符串的异或扫描相等。

与 yz zy 检测类似，索引 i 处的左异或扫描必须等于索引长度处的右异或扫描-i xor 右异或扫描长度 i 是 y 的长度。

具有友好属性的更强散列将使病态情况不那么明显，但异或扫描应该有很大帮助。

异或扫描是所有先前字符的异或。这可以在字符串中就地完成，将每个字符替换为其自身和所有先前字符的异或。操作很容易反转，并且需要线性时间。

字符串比较需要一点小心，但您只需将每个扫描条目与上一次扫描进行异或运算即可获得原始字符。

Here is an implementation of the xor-optimized version. Experimentally 它执行 ~5 n^2 个字符操作，但它会有 n^3 种情况。

两个字符串 XYZ 和 XZY

Two strings as XYZ and XZY

c++

lcs