diffをつくる(3) -前編

「O(ND)」というのは、この手続きにかかる計算量のことですが、それがそのままアルゴリズムのことをさす言葉になっているようです。
詳しい解説はこのページなどをみてもらうとして、ともかく実装。

#include <string>
#include <vector>
#include <stdexcept>

int snake(int x, int y, const std::string& str_a, const std::string& str_b)
{
    while((x < str_a.size()) && (y < str_b.size()) && (str_a[x] == str_b[y]))
    {
        ++x;
        ++y;
    }
    return y;
}

int ond(const std::string& str_a, const std::string& str_b)
{
    const int m = str_a.size();
    const int n = str_b.size();

    const int& offset = m;

    std::vector<int> v(m + n + 1);

    for(int d = 0; d <= m + n; ++d)
    {
        for(int k = -d; k <= d; k += 2)
        {
            if((k < -m) || (n < k))
            {
                continue;
            }

            int y;
            if((k == -d) || (k == -m))
            {
                y = v[k + 1 + offset];
            }
            else if((k == d) || (k == n))
            {
                y = v[k - 1 + offset] + 1;
            }
            else if(v[k - 1 + offset] < v[k + 1 + offset])
            {
                y = v[k + 1 + offset];
            }
            else
            {
                y = v[k - 1 + offset] + 1;
            }

            y = snake(y - k, y, str_a, str_b);

            v[k + offset] = y;

            if(((y - k) >= m) && (y >= n))
            {
                return d;
            }
        }
    }
    throw std::runtime_error("not found");
}

#include <iostream>

int main(int argc, char* argv[])
{
    if(argc != 3)
    {
        std::cout << argv[0] << " <str_a> <str_b>\n";
        return 0;
    }

    try
    {
        std::cout << ond(argv[1], argv[2]) << "\n";
    }
    catch(const std::exception& e)
    {
        std::cerr << e.what() << std::endl;
    }

    return 0;
}

実行例。

$ ./ond string strength
4

実のところ、このコードでは最小の編集回数SED(Shortest Edit Distance)が求まるだけなので、diffを求めるには経路を記憶しておかないといけません。記録された経路は起点からツリーになっているので、そのうち終点まで到達した枝を選んでやることでdiffを求めることができます。

後編につづく。

追記

最初に投稿した内容にミスがありました。修正しました。