Здравствуйте, Artazor, Вы писали:


A>2) Найти наименьшую подстроку из Haystack содержащую данную подпоследовательноть Common: Chunk = "RX153afla"
A>Товарищи, как это распилить за O(n*m) ?

Делай как в классическом алгоритме с подсчётом расстояния Левенштейна. Отличия:

• Нельзя добавлять символы;
• Нельзя заменять символы (но по прежнему есть сдвиг по совпадению);
• Можно начинать с любого символа из haystack — на соответсвующей стороне матрицы будут нули (а не 0,1,2,3,… как в Левенштейне);
• Можно закончить на любом символе из haystack (а не только в углу матрицы).

Пример модификации:

#include <vector>
#include <string>
#include <limits>
#include <iostream>

struct Cell {
    size_t cost;
    bool accept;
};

typedef std::vector<Cell> CellVector;
typedef std::vector<CellVector> CellMatrix;

size_t ld(const std::string& haystack, const std::string& common) {
    const size_t len_haystack = haystack.size();
    const size_t len_common = common.size();
    CellMatrix m(len_common + 1, CellVector(len_haystack + 1));
    const size_t inf = std::numeric_limits<size_t>::max();

    // вычисление расстояния
    for (size_t j = 0; j <= len_haystack; ++j)
        m[0][j] = Cell({0, false});
    for (size_t nc = 1; nc <= len_common; ++nc) {
        m[nc][0] = Cell({inf, false});
        char char_common = common[nc - 1];
        for (size_t j = 1; j <= len_haystack; ++j) {
            char char_haystack = haystack[j - 1];
            const Cell& skip = m[nc][j - 1];
            const Cell& shift = m[nc - 1][j - 1];
            size_t skip_cost = (skip.cost == inf) ? inf : skip.cost + 1;
            size_t shift_cost = (char_common == char_haystack) ? shift.cost : inf;
            size_t cost = std::min(inf, std::min(skip_cost, shift_cost));
            m[nc][j].cost = cost;
            m[nc][j].accept = (cost == shift_cost);
        }
    }

    // восстановление пути
    size_t hpos = 0;
    for (size_t h = 0; h <= len_haystack; ++h)
        if (m[len_common][h].cost < m[len_common][hpos].cost)
            hpos = h;
    size_t cost = m[len_common][hpos].cost;
    if (cost == inf)
        return cost;
    std::vector<size_t> indices;
    for (size_t nc = len_common; nc > 0; --nc) {
        while (1) {
            const Cell& c = m[nc][hpos--];
            if (c.accept) {
                indices.push_back(hpos);
                break;
            }
        }
    }

    // визуализация
    std::cout << haystack << std::endl;
    std::string v(len_haystack, '_');
    for (size_t i : indices)
        v[i] = haystack[i];
    std::cout << v << std::endl;
    return cost;
}

int main() {
    const char* a = "Client complains about RX153afla, status is red";
    const char* b = "RX153aa";
    size_t r = ld(a, b);
    std::cout << r << std::endl;
    return 0;
}