C++ string diff (а-ля Python difflib)

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

Это может сработать, по крайней мере, он проходит ваш демонстрационный тест: Обновлено: я внес некоторые изменения, чтобы решить некоторые проблемы с индексацией строк. Я считаю, что сейчас должно быть хорошо.

#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 состоит только из цифр.

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

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

@Evan Teran: похоже, мы делали это параллельно - у меня заметно менее читаемая реализация 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;
}

Как насчет использования чего-то вроде 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);
}