查找多個字符串的公共前綴的最有效方法

查找許多字符串的公共前綴的最有效方法是什麼？查找多個字符串的公共前綴的最有效方法

例如：

對於這組串

/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/

我想炭對比，以避免焦炭的。

來源

2012-06-18 texai

您正在使用哪種語言？ –

[查找字符串數組的常見前綴]的可能的重複（http://stackoverflow.com/questions/1336207/finding-common-prefix-of-array-of-strings） –

你不能避免至少通過通用部分去尋找公共前綴。

我不認爲這需要任何花哨的算法。只需跟蹤當前的通用前綴，然後通過將當前前綴與下一個字符串進行比較來縮短前綴。

由於這是所有字符串的通用前綴，因此可能會以空字符串（無共同前綴）結尾。

來源

2012-06-18 01:32:20 nhahtdh

我不確定你的意思是避免字符比較，但你至少需要閱讀每個字符串的公共前綴，所以下面的算法是最好的，你可以實現（只是遍歷直到它們偏離或直到達到當前最長的前綴計數爲止）：

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-18 01:34:30

查找多個字符串的公共前綴的最有效方法

回答

相關問題