diffをつくる

わけあって、diffを自作中。で、いろいろネット上で情報を集めている最中。
検索をかけてみるとこのページがあちこちからリンクされていたので、読んでいるんですが…後半部分がまだよくわかりません。
仕方がないので、理解したところまでコードに変換しているところ。

まずは、一番ベタな方法で経路を検索する…ための情報を作るコード。

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>

typedef std::vector<std::vector<int> > Grid;

void showGrid(const Grid& grid)
{
    for(std::size_t row = 0; row < grid.size(); ++row)
    {
        for(std::size_t col = 0; col < grid[row].size(); ++col)
        {
            std::cout << grid[row][col] << " ";
        }
        std::cout << "\n";
    }
}

void diff(const std::string& str_a, const std::string& str_b)
{
    Grid grid(str_a.size() + 1);
    for(std::size_t i = 0; i < grid.size(); ++i)
    {
        grid[i].resize(str_b.size() + 1);
    }

    for(std::size_t row = 0; row < grid.size(); ++row)
    {
        grid[row][0] = row;
    }

    for(std::size_t col = 0; col < grid[0].size(); ++col)
    {
        grid[0][col] = col;
    }

    for(std::size_t row = 1; row < grid.size(); ++row)
    {
        for(std::size_t col = 1; col < grid[row].size(); ++col)
        {
            int d = std::min(grid[row - 1][col] + 1, grid[row][col - 1] + 1);
            if(str_a[row - 1] == str_b[col - 1])
            {
                d = std::min(d, grid[row - 1][col - 1]);
            }
            grid[row][col] = d;
        }
    }

    showGrid(grid);
}

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

    return 0;
}

実行例

$ ./my_diff1 string strength
0 1 2 3 4 5 6 7 8 
1 0 1 2 3 4 5 6 7 
2 1 0 1 2 3 4 5 6 
3 2 1 0 1 2 3 4 5 
4 3 2 1 2 3 4 5 6 
5 4 3 2 3 2 3 4 5 
6 5 4 3 4 3 2 3 4 

右下の「4」というのが文字列Aから文字列Bに変換するのにかかる操作(削除or追加)の回数。これで右下から左上へ最短経路をたどれば、操作をどんな順でたどればいいかわかる、はず。

次回につづく。