我被問到這個問題。如果n是第一個字符串的長度,m是第二個字符串的長度,我只能想到O(nm)算法。從第二個字符串中刪除第一個字符串中所有字符的最有效方法?
0
A
回答
4
那麼,你可以在O(n + m)中做到這一點。只需創建一個參考表,顯示第一個字符串中是否存在字符。類似這樣的(僞代碼,沒有特定的語言)
// fill the table
for (int i = 0; i < a.length; ++i) {
characterExists[a[i]] = true;
}
// iterate over second string
for (int i = 0; i < b.length; ++i) {
if !characterExists[b[i]] {
// remove char (or do whatever else you want)
}
}
1
你檢查了Boyer-Moore String Search Algorithm?
的最壞情況找到所有出現 在文本大約需要3 * N 比較,因此複雜性是 O(n)時,文本 無論是否包含匹配或沒有。這 證明需要幾年才能確定。在 年算法設計, 1977年,最大數量的 比較顯示不再是 比6 * N;在1980年它被證明是 不超過4 * N,直到科爾的結果 在九月1991年
C實現:
#include <limits.h>
#include <string.h>
#define ALPHABET_SIZE (1 << CHAR_BIT)
static void compute_prefix(const char* str, size_t size, int result[size]) {
size_t q;
int k;
result[0] = 0;
k = 0;
for (q = 1; q < size; q++) {
while (k > 0 && str[k] != str[q])
k = result[k-1];
if (str[k] == str[q])
k++;
result[q] = k;
}
}
static void prepare_badcharacter_heuristic(const char *str, size_t size,
int result[ALPHABET_SIZE]) {
size_t i;
for (i = 0; i < ALPHABET_SIZE; i++)
result[i] = -1;
for (i = 0; i < size; i++)
result[(size_t) str[i]] = i;
}
void prepare_goodsuffix_heuristic(const char *normal, size_t size,
int result[size + 1]) {
char *left = (char *) normal;
char *right = left + size;
char reversed[size+1];
char *tmp = reversed + size;
size_t i;
/* reverse string */
*tmp = 0;
while (left < right)
*(--tmp) = *(left++);
int prefix_normal[size];
int prefix_reversed[size];
compute_prefix(normal, size, prefix_normal);
compute_prefix(reversed, size, prefix_reversed);
for (i = 0; i <= size; i++) {
result[i] = size - prefix_normal[size-1];
}
for (i = 0; i < size; i++) {
const int j = size - prefix_reversed[i];
const int k = i - prefix_reversed[i]+1;
if (result[j] > k)
result[j] = k;
}
}
/*
* Boyer-Moore search algorithm
*/
const char *boyermoore_search(const char *haystack, const char *needle) {
/*
* Calc string sizes
*/
size_t needle_len, haystack_len;
needle_len = strlen(needle);
haystack_len = strlen(haystack);
/*
* Simple checks
*/
if(haystack_len == 0)
return NULL;
if(needle_len == 0)
return haystack;
/*
* Initialize heuristics
*/
int badcharacter[ALPHABET_SIZE];
int goodsuffix[needle_len+1];
prepare_badcharacter_heuristic(needle, needle_len, badcharacter);
prepare_goodsuffix_heuristic(needle, needle_len, goodsuffix);
/*
* Boyer-Moore search
*/
size_t s = 0;
while(s <= (haystack_len - needle_len))
{
size_t j = needle_len;
while(j > 0 && needle[j-1] == haystack[s+j-1])
j--;
if(j > 0)
{
int k = badcharacter[(size_t) haystack[s+j-1]];
int m;
if(k < (int)j && (m = j-k-1) > goodsuffix[j])
s+= m;
else
s+= goodsuffix[j];
}
else
{
return haystack + s;
}
}
/* not found */
return NULL;
}
+0
這個算法做了一些完全不相關的事情嗎? – Ishtar 2010-09-02 10:36:06
相關問題
- 1. 從第一個字符串中刪除第二個字符串的所有實例
- 2. 刪除字符串中的最後一個字符和第一個字符
- 3. Python:從第一個數字字符中刪除字符串
- 4. 從八度字符串中刪除第一個字符
- 5. 如何從字符串中刪除第一個和最後一個字符
- 6. 如何從字符串中刪除所有字符,從第一個非字母字符開始?
- 7. 如何刪除PHP中的字符串的第一個字符?
- 8. C# - 從另一個字符串中刪除第一個子字符串的最簡單方法
- 9. 字符串的第一個字符和最後一個字符
- 10. 比較Android的第二個字符串中的第一個字符串
- 11. 如何刪除字符串中包含第3個斜槓的所有字符?
- 12. Autohotkey:從字符串中刪除所有單個字符
- 13. 刪除字符串的3個第一個字符
- 14. 從給定的字符串中只刪除第一個字
- 15. 替換字符串中第一個字符後的所有字符
- 16. 從C字符串中剝離第一個字符和最後一個字符
- 17. VBA從字符串中刪除HTML標記僅刪除第一個字符
- 18. 最快如果有多個不同的字符串是第二個字符串的一個子檢查方法
- 19. cout:最後一個字符串覆蓋第一個字符串
- 20. 從最後一個逗號字符串中刪除所有字符起
- 21. F# - 刪除字符串中的第一個字符後的重複字符
- 22. Windows批處理 - 從字符串中刪除第一個字
- 23. 紅寶石從字符串中刪除第一個字
- 24. 子字符串取第4個字符後的所有字母
- 25. 檢查的第二個字符串中的所有字符是否與存在於第一個字符串中的字符匹配至少一次
- 26. 剝字符串的第一個字符
- 27. 渦輪pascal從字符串中刪除第二個空格
- 28. 如何刪除字符串的第一個字符?
- 29. 刪除字符串的第一個字符如果它等於
- 30. 獲取並刪除字符串的第一個字符
是否要刪除所有字符,或所有出現?例如應該從「BABY」中刪除「AB」返回「Y」或「BY」? – 2010-09-02 10:09:43