Две строки как XYZ и XZY
У меня есть две строки, обе одинаковой длины. И я должен проверить, могут ли они быть выражены как XYZ и XZY, где Y и Z не пусты.
Мое решение состоит в том, чтобы «съесть» одни и те же первые буквы обеих строк, а затем найти Longest Common Substring для отдыха. Затем проверьте, равны ли остаток первой и второй строки (без LCS). Проблема в том, что я слышал об алгоритме сложности памяти O (N) для этого, но все, что я нашел, это O (MN). У меня ограниченная память, поэтому это важно для меня.
Второе решение — использовать регулярное выражение «(. *) (. +) (. +) \ 1 \ 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;
}
Если память очень важна для вас, вы можете избежать подстрок, сравнивая char с char. Например:
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;
}
Точно так же вы можете избежать строк x1, x2, y1 и y2, введя два одинаковых цикла for, где вместо этого вы сравниваете char-by-char.
Код будет сложнее читать и понимать, но он будет использовать меньше памяти.
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;
}
Другие решения
Во-первых, прекратите копировать вещи:
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) памяти.
время оптимизации.
Сделайте сканирование XOR. Теперь единственные длины x возможны те, что xor сканирует по этому индексу, а также XOR сканирование всех строк равны.
Точно так же для обнаружения yz zy, сканирование левого xor по индексу i должно равняться сканированию правого xor по длине индекса -i или x сканированию правого xor по длине, чтобы i было длиной y.
Более сильный хэш со все еще дружественными свойствами сделает патологические случаи менее очевидными, но сканирование xor должно помочь много.
Скан xor — это xor всех предыдущих символов. Это можно сделать на месте внутри строк, заменив каждый символ на xor самого себя и всех предыдущих символов. Операция легко инвертируется и занимает линейное время.
Сравнение строк требует некоторой осторожности, но вы просто присваиваете каждой записи сканирования предыдущее сканирование, чтобы получить исходный символ.
Вот является реализацией оптимизированной для xor версии. опытным путем это делает ~5 n^2 символьные операции, но у него будет n ^ 3 случаев.
Не проверено, пища для размышлений.
- Переверните вторую строку и присоедините к первой, например, XYZY’Z’X. (или наоборот)
- Найдите самый длинный возможный X == X ‘(здесь может потребоваться некоторое обсуждение алгоритма), где размер (X) <= len (XYZY’Z’X ‘) / 2
- Итерация от размера (X) до 0. В каждой итерации удаляйте X с обоих концов, чтобы строка была YZY’Z ‘, и убедитесь, что YZ == Y’Z’,
разбить строку посередине и вернуть True, если проверено. - После итерации верните false.