많은 문자열의 공통 접두사를 찾는 가장 효율적인 방법

Question

많은 문자열의 공통 접두사를 찾는 가장 효율적인 방법은 무엇입니까? 예를 들어

: 문자열

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

얻을 싶어이 세트의

.

Answer 1

공통 접두사를 찾으려면 적어도 일반적인 부품을 피해야합니다.

나는 어떤 멋진 알고리즘도 필요하지 않다고 생각합니다. 현재의 공통 접두사를 추적 한 다음 현재 접두사와 다음 문자열을 비교하여 접두사를 줄이십시오.

이것은 모든 문자열의 공통 접두사이므로 빈 문자열 (공통 접두사 없음)이 될 수 있습니다.

Answer 2

char 비교에 의한 char을 피하는 것이 확실하지 않지만 각 문자열에서 공통 접두어를 읽어야하므로 다음 알고리즘이 가장 좋습니다 (문자열이 벗어날 때까지 또는 현재 가장 긴 접두어 카운트에 도달 할 때까지) :

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);