C ++ string diff (а-ля библиотека Python) - PullRequest
Новая
       9

C ++ string diff (а-ля библиотека Python)

3 голосов
/ 06 ноября 2008

Я пытаюсь различить две строки, чтобы определить, отличаются ли они только в одном числовом подмножестве структуры строки; например, 

varies_in_single_number_field('foo7bar', 'foo123bar')
# Returns True, because 7 != 123, and there's only one varying
# number region between the two strings.

В Python я могу использовать difflib для этого: 

import difflib, doctest

def varies_in_single_number_field(str1, str2):
    """
    A typical use case is as follows:
        >>> varies_in_single_number_field('foo7bar00', 'foo123bar00')
        True

    Numerical variation in two dimensions is no good:
        >>> varies_in_single_number_field('foo7bar00', 'foo123bar01')
        False

    Varying in a nonexistent field is okay:
        >>> varies_in_single_number_field('foobar00', 'foo123bar00')
        True

    Identical strings don't *vary* in any number field:
        >>> varies_in_single_number_field('foobar00', 'foobar00')
        False
    """
    in_differing_substring = False
    passed_differing_substring = False # There should be only one.
    differ = difflib.Differ()
    for letter_diff in differ.compare(str1, str2):
        letter = letter_diff[2:]
        if letter_diff.startswith(('-', '+')):
            if passed_differing_substring: # Already saw a varying field.
                return False
            in_differing_substring = True
            if not letter.isdigit(): return False # Non-digit diff character.
        elif in_differing_substring: # Diff character not found - end of diff.
            in_differing_substring = False
            passed_differing_substring = True
    return passed_differing_substring # No variation if no diff was passed.

if __name__ == '__main__': doctest.testmod()

Но я понятия не имею, как найти что-то вроде difflib для C ++. Альтернативные подходы приветствуются. :)

Ответы [ 5 ]

2 голосов
/ 06 ноября 2008

Это может сработать, оно хотя бы пройдет ваш демонстрационный тест: РЕДАКТИРОВАТЬ: я сделал несколько модификаций для решения некоторых проблем индексации строк. Я считаю, что это должно быть хорошо сейчас. 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cctype>

bool starts_with(const std::string &s1, const std::string &s2) {
    return (s1.length() <= s2.length()) && (s2.substr(0, s1.length()) == s1);
}

bool ends_with(const std::string &s1, const std::string &s2) {
    return (s1.length() <= s2.length()) && (s2.substr(s2.length() - s1.length()) == s1);
}

bool is_numeric(const std::string &s) {
    for(std::string::const_iterator it = s.begin(); it != s.end(); ++it) {
        if(!std::isdigit(*it)) {
                return false;
        }
    }
    return true;
}

bool varies_in_single_number_field(std::string s1, std::string s2) {

    size_t index1 = 0;
    size_t index2 = s1.length() - 1;

    if(s1 == s2) {
        return false;
    }

    if((s1.empty() && is_numeric(s2)) || (s2.empty() && is_numeric(s1))) {
        return true;
    }

    if(s1.length() < s2.length()) {
        s1.swap(s2);
    }

    while(index1 < s1.length() && starts_with(s1.substr(0, index1), s2)) { index1++; }
    while(ends_with(s1.substr(index2), s2)) { index2--; }

    return is_numeric(s1.substr(index1 - 1, (index2 + 1) - (index1 - 1)));

}

int main() {
    std::cout << std::boolalpha << varies_in_single_number_field("foo7bar00", "foo123bar00") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("foo7bar00", "foo123bar01") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("foobar00", "foo123bar00") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("foobar00", "foobar00") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("7aaa", "aaa") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("aaa7", "aaa") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("aaa", "7aaa") << std::endl;
    std::cout << std::boolalpha << varies_in_single_number_field("aaa", "aaa7") << std::endl;
}

По сути, он ищет строку, которая имеет 3 части, строка2 начинается с части1, строка2 заканчивается частью3, а часть2 - только цифры.

1 голос
/ 06 ноября 2008

Вы могли бы сделать специальный подход: вы ищете для сопоставления строк s и s ', где s = abc и s' = ab'c, а b и b 'должны быть двумя разными числами (возможно, пустыми) , Итак:

  1. Сравнивайте строки слева, символ за символом, пока не наберете разных персонажей, а затем остановитесь. Вы
  2. Аналогичным образом сравнивайте строки справа, пока вы не нажмете разные символы ИЛИ не нажмете этот левый маркер.
  3. Затем проверьте остатки посередине, чтобы увидеть, оба ли они числа.
1 голос
/ 06 ноября 2008

Возможно, это немного излишне, но вы можете использовать boost для взаимодействия с python. В худшем случае, difflib реализован на чистом питоне, и это не слишком долго. Должна быть возможность портировать с python на C ...

0 голосов
/ 06 ноября 2008

Как насчет использования чего-то вроде boost :: regex? 

// pseudo code, may or may not compile
bool match_except_numbers(const std::string& s1, const std::string& s2)
{
    static const boost::regex fooNumberBar("foo\\d+bar");
    return boost::match(s1, fooNumberBar) && boost::match(s2, fooNumberBar);
}
0 голосов
/ 06 ноября 2008

@ Эван Теран: похоже, что мы делали это параллельно - у меня заметно менее читаемая реализация O (n): 

#include <cassert>
#include <cctype>
#include <string>
#include <sstream>
#include <iostream>

using namespace std;

ostringstream debug;
const bool DEBUG = true;

bool varies_in_single_number_field(const string &str1, const string &str2) {
    bool in_difference = false;
    bool passed_difference = false;
    string str1_digits, str2_digits;
    size_t str1_iter = 0, str2_iter = 0;
    while (str1_iter < str1.size() && str2_iter < str2.size()) {
        const char &str1_char = str1.at(str1_iter);
        const char &str2_char = str2.at(str2_iter);
        debug << "str1: " << str1_char << "; str2: " << str2_char << endl;
        if (str1_char == str2_char) {
            if (in_difference) {
                in_difference = false;
                passed_difference = true;
            }
            ++str1_iter, ++str2_iter;
            continue;
        }
        in_difference = true;
        if (passed_difference) { /* Already passed a difference. */
            debug << "Already passed a difference." << endl;
            return false;
        }
        bool str1_char_is_digit = isdigit(str1_char);
        bool str2_char_is_digit = isdigit(str2_char);
        if (str1_char_is_digit && !str2_char_is_digit) {
            ++str1_iter;
            str1_digits.push_back(str1_char);
        } else if (!str1_char_is_digit && str2_char_is_digit) {
            ++str2_iter;
            str2_digits.push_back(str2_char);
        } else if (str1_char_is_digit && str2_char_is_digit) {
            ++str1_iter, ++str2_iter;
            str1_digits.push_back(str1_char);
            str2_digits.push_back(str2_char);
        } else { /* Both are non-digits and they're different. */
            return false;
        }
    }
    if (in_difference) {
        in_difference = false;
        passed_difference = true;
    }
    string str1_remainder = str1.substr(str1_iter);
    string str2_remainder = str2.substr(str2_iter);
    debug << "Got to exit point; passed difference: " << passed_difference
        << "; str1 digits: " << str1_digits
        << "; str2 digits: " << str2_digits
        << "; str1 remainder: " << str1_remainder
        << "; str2 remainder: " << str2_remainder
        << endl;
    return passed_difference
        && (str1_digits != str2_digits)
        && (str1_remainder == str2_remainder);
}

int main() {
    assert(varies_in_single_number_field("foo7bar00", "foo123bar00") == true);
    assert(varies_in_single_number_field("foo7bar00", "foo123bar01") == false);
    assert(varies_in_single_number_field("foobar00", "foo123bar00") == true);
    assert(varies_in_single_number_field("foobar00", "foobar00") == false);
    assert(varies_in_single_number_field("foobar00", "foobaz00") == false);
    assert(varies_in_single_number_field("foo00bar", "foo01barz") == false);
    assert(varies_in_single_number_field("foo01barz", "foo00bar") == false);
    if (DEBUG) {
        cout << debug.str();
    }
    return 0;
}
...