2

多くの文字列の共通のプレフィックスを見つける最も効率的な方法は何ですか?

例えば：

この文字列セットの場合

/home/texai/www/app/application/cron/logCron.log
/home/texai/www/app/application/jobs/logCron.log
/home/texai/www/app/var/log/application.log
/home/texai/www/app/public/imagick.log
/home/texai/www/app/public/status.log

手に入れたい/home/texai/www/app/

文字ごとの比較を避けたい。

4

2 に答える 2

2

共通のプレフィックスを見つけるために、少なくとも共通の部分を通過することは避けられません。

これには派手なアルゴリズムは必要ないと思います。現在の共通プレフィックスを追跡し、現在のプレフィックスを次の文字列と比較してプレフィックスを短縮します。

これはすべての文字列の共通プレフィックスであるため、空の文字列 (共通プレフィックスなし) になる可能性があります。

于 2012-06-18T01:32:20.753 に答える
1

文字ごとの比較を避けることの意味がわかりませんが、少なくとも各文字列から共通のプレフィックスを読み取る必要があるため、次のアルゴリズムが達成できる最善の方法です(文字列が逸脱するまで繰り返します)または現在の最長プレフィックス数に達するまで):

List<string> list = new List<string>()
{
    "/home/texai/www/app/application/cron/logCron.log",
    "/home/texai/www/app/application/jobs/logCron.log",
    "/home/texai/www/app/var/log/application.log",
    "/home/texai/www/app/public/imagick.log",
    "/home/texai/www/app/public/status.log"
};

int maxPrefix = list[0].Length;
for(int i = 1; i < list.Count; i++)
{
    int pos = 0;
    for(; pos < maxPrefix && pos < list[i].Length && list[0][pos] == list[i][pos]; pos++);

    maxPrefix = pos;
}

//this is the common prefix
string prefix = list[0].Substring(0, maxPrefix);
于 2012-06-18T01:34:30.693 に答える