KMP算法的時間複雜度

我想用KMP算法實現strstr。這是維基百科中給出的算法。 KMP算法的時間複雜度爲O（n），其中n是較大字符串的大小。KMP算法的時間複雜度

vector<int> KMP(string S, string K) 
{ 
    vector<int> T(K.size() + 1, -1); 
    vector<int> matches; 

    if(K.size() == 0) 
    { 
     matches.push_back(0); 
     return matches; 
    } 
    for(int i = 1; i <= K.size(); i++) 
    { 
     int pos = T[i - 1]; 
     while(pos != -1 && K[pos] != K[i - 1]) pos = T[pos]; 
     T[i] = pos + 1; 
    } 

    int sp = 0; 
    int kp = 0; 
    while(sp < S.size()) 
    { 
     while(kp != -1 && (kp == K.size() || K[kp] != S[sp])) kp = T[kp]; 
     kp++; 
     sp++; 
     if(kp == K.size()) matches.push_back(sp - K.size()); 
    } 

    return matches; 
}

我不明白這個算法的複雜度是如何O（n）。任何人都可以解釋這個代碼的複雜性是O（n）嗎？

來源

2014-02-09 Crusher

你認爲這會是什麼，並解釋？ – herohuyongtao

我認爲填充數組T是O（m^2），第二部分是O（n * m），其中m是較小字符串的大小。 – Crusher

這可能有助於：[wiki：KMP]（http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm）。 – herohuyongtao

我假設你擔心兩種情況下的內部循環可能會在每次外循環迭代中執行多達m次，導致你提到的最壞情況的複雜性。事實上，這不可能發生。

感應地看第一個循環通知，因爲T []初始化爲-1，所以我們有T [0] < 0和T [1] < 1，...你可以看到我們事實上有T [i] <我，這是有道理的，因爲T [i]是一個指向我們正在搜索的字符串的指針。

現在轉到第二個嵌套循環，看看每個外循環迭代只增加一次kp，內循環只能減少它。由於kp約束在-1以下，從0開始，在整個生命週期中，我們總共只能執行一次內循環迭代，而不是外循環迭代，因爲否則kp最終會比 - 1。所以第二個嵌套循環只需要花費O（n）。

第一個嵌套循環看起來比較棘手，直到你注意到在外循環開始時從T [i - 1]讀取pos，然後在末尾寫爲T [i] = pos + 1，所以pos是相當於我們剛剛分析的嵌套循環中的kp，並且相同的論證顯示成本最多爲O（K.size（））。

來源

2014-02-09 05:41:23 mcdowella

KMP算法的時間複雜度

回答

相關問題