효율적인 문자열 비교

Question

나는 문자 변화에 따라 주어진 포인트를 줄 수있는 효율적인 문자열 비교 알고리즘을 구현하려고 노력 해왔다. 예를 들어

는 :

String #1: abcd 
String #2: acdb 
Initial Point: 0 

문자열 # 여기에서이 문자 c 2에서 1로의 인덱스를 변경, d는 4에서 그 (2-1=1 및 4-3=1) 모두가 합계 3으로 인덱스를 변경 초기 점 2 점. 숙제가 아니거나, 각 캐릭터를 하나 하나씩 비교하는 기본적인 for 루프를 만들고 싶지 않고 효율적인 방법 (해싱 등)이 적용될 수 있는지 물어보고 싶었습니까?

Answer 1

간단한 것을 지나치게 복잡하게 만듭니다. 각각의 캐릭터를 비교하는 것보다 더 효율적으로 일할 수는 없습니다. 차이점을 찾은 첫 번째 캐릭터에서 비교를 중단하십시오. 기본적으로는 strcmp입니다. 두 가지 길이가 다른 경우 (예 : std::string 또는 다른 계산 된 문자열을 사용할 때와 같이) 두 문자열의 길이를 이미 알고있는 경우이를 수행 할 수있는 유일한 일반적인 최적화가 있습니다.

Answer 2

당신이 정말로 원하는 것은 Levenshtein 거리 같은 것입니다 (정확히는 그런 것은 아닙니다). 여기에 첫 번째 커팅이 있습니다. 그것은 무엇을

은 B일치하는지 의 모든 가능한 재 배열의 게임 트리를 거리에 있습니다. 비용을 각각의 재배치와 연관 짓고, 예산이으로 줄었습니다.

바깥 쪽 루프가 먼저 예산의 0으로 걷기 때문에 정확한 일치 만 허용됩니다.

성공하지 못하면 예산 한도로 1 회의 재배치 만 포함 된 모든 일치를 찾습니다.

성공하지 못하면 2의 예산으로 걷습니다. 이 일치하기

, 그것은 정수 의 각 요소가 교환되어 얼마나 말하고 델타의 어레이를 유지한다. 성공을 거둘 때마다 somwhow가 델타 배열을 인쇄합니다. 그리고 그것은 그 매치를 얻기 위해 어떤 스왑이 수행되었는지 기록한 것입니다.

void walk(char* a, char* b, int* delta, int budget, int& nSuccess){ 
    delta[0] = 0; 
    if (budget < 0) return; 
    if (a[0] == '\0' && b[0] == '\0'){ // end of both strings 
    nSuccess++; 
    // print out the deltas 
    return; 
    } 
    if (a[0] == '\0') return; // excess chars in b 
    if (b[0] == '\0') return; // excess chars in a 
    if (a[0] == b[0]){ // first chars are equal, move to next 
    walk(a+1, b+1, delta+1, budget, nSuccess); 
    return; 
    } 
    for (int i = 1; a[i] != '\0'; i++){ 
    delta[0] = i; 
    swap(a[0], a[i]); 
    if (a[0] == b[0]){ 
     walk(a+1, b+1, delta+1, budget-1, nSuccess); 
    } 
    swap(a[0], a[i]); 
    delta[0] = 0; 
    } 
} 

void top(char* a, char* b){ 
    int nSuccess = 0; 
    int delta[512]; 
    for (int budget = 0; nSuccess==0; budget++){ 
    walk(a, b, budget, delta, nSuccess); 
    } 
} 

알고리즘의 성능은 N에서 지수 함수이며, N은 문자열을 일치시키는 데 필요한 재배치의 최소 수입니다. 따라서 각 문자열의 문자 수가 각각 동일해야합니다 ( )는 것을 확인한 후 다시 정렬해야합니다.