代码编辑器搜索替换功能实现详解

/* 简单但低效，逐字符比较 */ int naive_search(const char *text, const char *pat) { size_t n = strlen(text), m = strlen(pat); for (size_t i = 0; i <= n - m; i++) { if (memcmp(&text[i], pat, m) == 0) return i; /* 找到返回位置 */ } return -1; }

/* 预处理坏字符表 */ void preprocess_bad_char(const char *pat, int bad[256]) { int m = strlen(pat); for (int i = 0; i < 256; i++) bad[i] = m; for (int i = 0; i < m - 1; i++) bad[(unsigned char)pat[i]] = m - 1 - i; } int boyer_moore(const char *text, const char *pat) { int bad[256]; preprocess_bad_char(pat, bad); int n = strlen(text), m = strlen(pat); int s = 0; while (s <= n - m) { int j = m - 1; while (j >= 0 && pat[j] == text[s + j]) j--; if (j < 0) return s; s += max(1, j - bad[(unsigned char)text[s + j]]); } return -1; }

/* 替换所有匹配项 */ char *replace_all(const char *text, const char *find, const char *replace) { /* 1. 统计匹配数量和总增长长度 */ int count = 0; size_t find_len = strlen(find); size_t replace_len = strlen(replace); size_t pos = 0; const char *p = text; while ((p = strstr(p, find)) != NULL) { count++; p += find_len; } /* 2. 分配新缓冲区 */ size_t new_len = strlen(text) + count * (replace_len - find_len) + 1; char *result = malloc(new_len); char *dst = result; const char *src = text; /* 3. 逐个替换 */ while ((p = strstr(src, find)) != NULL) { memcpy(dst, src, p - src); dst += p - src; memcpy(dst, replace, replace_len); dst += replace_len; src = p + find_len; } strcpy(dst, src); return result; }

/* 使用 POSIX 正则 */ #include int regex_search(const char *text, const char *pattern, int *matches, int max) { regex_t re; int ret = regcomp(&re, pattern, REG_EXTENDED); if (ret) return -1; regmatch_t m[1]; int count = 0; const char *p = text; while (count < max && !regexec(&re, p, 1, m, 0)) { matches[count++] = p - text + m[0].rm_so; p += m[0].rm_eo; } regfree(&re); return count; }