高效的字符串比較

我一直在嘗試實現一種高效的字符串比較算法，根據字符變化給出點。高效的字符串比較

例如：

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

在這裏字符串＃2字符c改變了它的指數從2至1，且d改變了它的索引爲4至3.他們兩個（2-1=1和）的合計爲2分爲初始點。不是一個家庭作業或任何東西，我只是不想創建一個基本的循環逐一比較每個字符，並想問是否可以應用任何有效的方法（如散列等）？

來源

2011-12-24 Ali

這個問題還不清楚，但也許你正在考慮像「編輯距離」或「Levenshtein距離」之類的東西。 – 2011-12-24 14:27:16

你究竟在尋找什麼？字符串也可以重複字符嗎？如果是這樣，你怎麼知道第二個字符串中的'c'是第一個'c'字符？ – 2011-12-24 14:49:08

你太過簡單了。你不可能比比較每個角色更有效率，並且在你發現不同的第一個角色處停止比較 - 這基本上是strcmp所做的。如果您已經知道兩個字符串的長度（如使用std::string或其他計數的字符串時發生的情況），則可以做的唯一典型優化是，如果兩個長度不同，則立即確定它們不等。

來源

2011-12-24 14:29:02

我之所以堅持有效的解決方案而不是簡單的字符串比較，是因爲我必須計算字符串＃1的每個排列的字符串更改。如果字符串是'abc'，我計算'acb'，'bca'，'bac'，'cab'，'cba' – Ali 2011-12-24 14:32:45

@rolandbishop：你應該澄清你的問題... – 2011-12-24 14:43:34

@roland：究竟是什麼你試圖達到？爲了測試兩個琴絃是否是彼此的排列，可以例如計算每個字符在字符串中出現的頻率。如果所有字符數相等，字符串就是彼此的排列。 – Philipp 2011-12-24 14:53:05

這聽起來像你真正想要的是像Levenshtein距離（但不完全是這樣）。這是第一次切割。

它能做什麼是走的一個所有可能的重排的博弈樹，看它們是否匹配b。它將成本與每次重新排列聯繫起來，表示爲下降的預算。

外層循環首先預算爲0，因此只允許完全匹配。

如果沒有成功，那麼它的預算爲1，找到只包含一個重排的所有匹配。

如果沒有成功，那麼它的預算爲2，依此類推。

作爲匹配，它保持整數增量，告訴多遠的一個每個元素已被交換的陣列。每當它獲得成功時，它就會打印出該增量數組，這就是您爲了獲得該匹配而進行的交換的記錄。

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是使字符串匹配所需的最小重新排列次數。所以它可能不應該使用，直到您確認每個字符串具有相同數字的每個字符，，並且只有在您需要查看重新排列記錄時才使用它。

來源

2011-12-24 16:23:55

非常感謝您的詳細解答。我會試試看！ – Ali 2011-12-24 18:51:40

高效的字符串比較

回答

相關問題