我辭書範圍的列表，例如 [a,an) [an,bb) [bb,d) [c,h) 給出一個字符串說apple，我需要找到它屬於哪個範圍。在這種情況下，它處於第二個範圍。如果字符串可能屬於多個範圍，則需要返回第一個。例如：cat應該返回範圍3而不是範圍4。搜索字符串列表的字符串範圍
蠻力的方法是按順序遍歷列表並檢查字符串是否適合在那裏。 更好的方法是首先解決重疊問題，對範圍進行排序並進行二分搜索。 有關進一步優化算法的任何建議？還歡迎C++的實現提示。這種邏輯恰好發生在關鍵執行路徑上，並且必須很快。
更新： 是的，可能存在範圍的空白。 是二進制搜索可以使它O(log(n))。有沒有我能想出一個散列，並使其更好？哈希如何看起來像？我們可以假設我們在所有字符串和範圍中只有小寫字符。
我想起了一個解決方案，可能是您可以對蘋果這個詞進行排序，並確定以a-z順序排列的最後一個字符。只要檢查你的範圍內的一個字符。思考更多...
某種類型的每個範圍的開始索引，也許是一個二叉樹，可能是一個好主意。不知道你是否需要索引到每個範圍的末尾，除非可能有差距。
這裏是你應該做的：
首先排序在字典順序對於他們的開端範圍。然後，你應該對它們進行以下預處理 - 對於每個範圍，它的開始位置都是從開始和前一個範圍的末端開始（如果這使得當前範圍爲空，則忽略它）。你這樣做是因爲如果一個單詞在前一個範圍的末尾之前，那麼它將屬於前面的一些範圍，並且永遠不會被分類到當前範圍內。在預處理之後，所有範圍都不重疊，因此您搜索的每個單詞最多隻屬於其中一個單詞。因此，所有您需要做的就是對O（log（n））複雜度的結果預處理範圍執行二進制搜索。我懷疑你可以爲這個問題取得更好的複雜性。
使每個非重疊範圍指向一個原始範圍，並且是工作完成。 – UmNyobe 2012-02-17 13:16:43
好吧，當然你需要以某種方式保持原始範圍，以便你可以返回你屬於哪個原始範圍。 – 2012-02-17 13:17:32
如果您有空餘的內存並且被限制爲小寫，則可以構建多路樹。頂部節點有一個26個指針的數組。如果沒有範圍以該字符開始，則指針爲空。如果以該字符開頭的所有單詞落入該範圍，則它們指向一個範圍，並且如果範圍在後續字符上拆分，則指向另一個節點。 （[aa-ap]，[ar-bl];'a'項將指向另一個節點，其中條目'a'到'p'指向範圍1，條目'q'爲空，'r'直到'z'指向範圍2.）
這應該是O（max（range_specifier））。
你可能會通過「網格化」來解決這個問題。
使用與第一個字母對應的26個條目的數組。每個bin都包含與其具有非空交集的範圍列表。像
'a' -> [a,an) [an,bb), 'b' -> [an,bb) [bb,d), 'c' -> [bb,d) [c,h) ...
您可以輕鬆地概括想法的幾個字母
'aaa' -> [a,an), 'aab' -> [a,an), 'aac' -> [a,an) ...
這多少縮短範圍列表前綴受審，尤其是如果有一點重疊，以犧牲存儲和預處理時間。
一個特殊的慣例可以用來表示一個bin被完全覆蓋。
快樂的分佈可以導致O（1），我想。
我不驚訝你的一系列範圍可以用trie（http://en.wikipedia.org/wiki/Trie）表示。一旦填充了trie，查詢時間不應超過最長範圍的長度或查詢字符串的長度。
這在查詢時間方面是最優的（實際上在您的計算模型中爲O（1））。
我的方法將是
所以該方法可以是：
由於這種方法是一種樹搜索，它具有O（日誌（N））的複雜性。
UPDATE：關於第二個想法，位圖是不存儲用戶名單或結果好辦法。鏈表（實際上是兩個）更好。代碼是300行。我應該在這裏發佈嗎？
#include <limits.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#define COUNTOF(a) (sizeof a/sizeof a[0])
#define WANT_DUPLICATES 0
struct range {
/* separate linked lists for {lo,hi})
** for limits that this range participates in. */
struct range *next_lo;
struct range *next_hi;
unsigned num;
char *str_lo, *str_hi;
} ranges[] =
{{NULL,NULL,0, "a","an"}, {NULL,NULL,1, "an", "bb"}
,{NULL,NULL,2, "bb", "d"}, {NULL,NULL,3, "c", "h"}
,{NULL,NULL,4, "bb", "c"}, {NULL,NULL,5, "c", "d"}
};
#define NRANGE COUNTOF(ranges)
void add_range(struct range *pp);
void list_dmp(FILE *fp, int isupper, struct range *bp);
struct treetwo {
struct treetwo *prev;
struct treetwo *next;
char *str;
struct range *list_lo; /* ranges that use str as lower limit */
struct range *list_hi; /* ranges that use str as upper limit */
};
struct treetwo *root = NULL;
struct treetwo ** find_hnd(struct treetwo **tpp, char *str);
void tree_dmp(FILE *fp, struct treetwo *tp, char *msg, unsigned indent);
struct result {
unsigned size;
unsigned used;
struct {
unsigned num;
unsigned mask;
} *entries;
};
#define MASK_BELOW_LO 1
#define MASK_ABOVE_LO 2
#define MASK_BELOW_HI 4
#define MASK_ABOVE_HI 8
int result_resize(struct result *res, unsigned newsize);
void init_structures(void);
struct result *find_matches (char *str);
unsigned update_state(struct result *rp, struct treetwo *tp, int isabove);
int main (void)
{
char buff[100];
struct result *res;
size_t pos;
unsigned idx;
static char *legend[4] = { "unknown", "below", "above", "impossible"};
init_structures();
tree_dmp(stderr, root, "Root", 0);
while (fgets (buff, sizeof buff, stdin)) {
pos=strcspn(buff, "\r\n");
buff[pos] = 0;
res = find_matches (buff);
for (idx=0; idx < res->used; idx++) {
unsigned num = res->entries[idx].num;
unsigned mask = res->entries[idx].mask;
fprintf(stdout, "[%u]Range%u %x: '%s' %s '%s' and '%s' %s '%s'\n"
, idx, num, mask
, buff, legend[mask & 3], ranges[num].str_lo
, buff, legend[(mask>>2) & 3], ranges[num].str_hi
);
}
}
return 0;
}
unsigned update_state(struct result *rp, struct treetwo *tp, int isabove)
{
struct range *p;
unsigned mask_lo, mask_hi;
unsigned hitcnt,idx;
/* State: (lower limit)
** 0 : unknown
** MASK_BELOW_LO: below limit
** MASK_ABOVE_LO: above limit
** 3: impossible
** State: (upper limit)
** 0 : unknown
** MASK_BELOW_HI: below limit
** MASK_ABOVE_HI: above limit
** c: impossible
** Combined states:
** required state 2|4 := 6
** 5: unreachable
** a: unreachable
** 9: impossible
** f: impossible
*/
if (!tp) return 0;
hitcnt=0;
mask_lo = (isabove>=0) ? MASK_ABOVE_LO : MASK_BELOW_LO;
mask_hi = (isabove>=0) ? MASK_ABOVE_HI : MASK_BELOW_HI;
fprintf(stderr , "Update_state(start{%s}, isabove=%d, mask=%x,%x)\n"
, tp->str , isabove, mask_lo, mask_hi);
fprintf(stderr , "Update_state(Lo=%s)=", tp->str);
list_dmp(stderr , 0, tp->list_lo);
idx=0;
for (p = tp->list_lo; p ; p = p->next_lo) {
unsigned num = p->num;
fprintf(stderr , "Update_state:[%u] |= %u", num, mask_lo);
for ( ;idx < rp->used;idx++) { if (rp->entries[idx].num >= num) break; }
if (idx < rp->used) {
fprintf(stderr , " Old was:%u\n", rp->entries[idx].mask);
rp->entries[idx].mask |= mask_lo;
if (rp->entries[idx].mask == (MASK_ABOVE_LO|MASK_BELOW_HI)) hitcnt++;
continue;
}
if (idx >= rp->used) {
if (rp->used >= rp->size && result_resize(rp, rp->size ? rp->size*2 : 8)) break;
fprintf(stderr , " New at:%u\n", idx);
rp->entries[idx].num = num;
rp->entries[idx].mask = mask_lo;
rp->used++;
}
}
fprintf(stderr , "Update_state(Hi=%s)=", tp->str);
list_dmp(stderr , 1, tp->list_hi);
idx=0;
for (p = tp->list_hi; p ; p = p->next_hi) {
unsigned num = p->num;
fprintf(stderr , "Update_state:[%u] |= %u", num, mask_lo);
for ( ;idx < rp->used;idx++) { if (rp->entries[idx].num >= num) break; }
if (idx < rp->used) {
fprintf(stderr , " Old was:%u\n", rp->entries[idx].mask);
rp->entries[idx].mask |= mask_hi;
if (rp->entries[idx].mask == (MASK_ABOVE_LO|MASK_BELOW_HI)) hitcnt++;
continue;
}
if (idx >= rp->used) {
if (rp->used >= rp->size && result_resize(rp, rp->size ? rp->size*2 : 8)) break;
fprintf(stderr , " New at:%u\n", idx);
rp->entries[idx].num = num;
rp->entries[idx].mask = mask_hi;
rp->used++;
}
}
return hitcnt;
}
struct result *find_matches (char *str)
{
int rc;
struct treetwo **hnd;
struct result *res = malloc (sizeof *res);
unsigned dst,src;
res->used=res->size=0; res->entries=0;
for (hnd= &root; *hnd; hnd = (rc < 0) ? &(*hnd)->prev : &(*hnd)->next) {
rc = strcmp(str, (*hnd)->str);
fprintf(stderr, "####\nStr=%s Node={%s} rc=%d\n"
, str, (*hnd)->str, rc);
list_dmp(stderr , 0, (*hnd)->list_lo);
list_dmp(stderr , 1, (*hnd)->list_hi);
rc = update_state(res, *hnd , rc);
#if WANT_DUPLICATES
continue;
#else
/* if we don't want duplicates we can bail out on the first match */
if (rc) break;
#endif
}
/* Now cleanup the results.
** Below(lower limit) and above(upper limit) and variations can be removed.
** Some results are incomplete, because one of there limits is out
** of reach (shadowed by a narrower range). We'll have to recompute these.
** The result structure is compacted: if entries are deleted, the remaining ones are shifted down.
** Note: part of this cleanup (removal of unreacheables) could be done in update_state(),
** that would keep the array with partial results as short as possible.
*/
for (dst=src=0; src < res->used; src++) {
int rc;
unsigned num = res->entries[src].num;
rescan:
switch (res->entries[src].mask & 0xf) {
default: break;
case 0: /* impossible */
goto rescan;
#if WANT_DUPLICATES
case MASK_ABOVE_LO:
rc = strcmp(str, ranges[num].str_hi);
res->entries[src].mask |= (rc >=0) ? MASK_ABOVE_HI : MASK_BELOW_HI;
goto rescan;
case MASK_BELOW_HI:
rc = strcmp(str, ranges[num].str_lo);
res->entries[src].mask |= (rc >=0) ? MASK_ABOVE_LO : MASK_BELOW_LO;
goto rescan;
#endif
case MASK_BELOW_HI|MASK_ABOVE_LO:
if (dst != src) res->entries[dst] = res->entries[src];
dst++;
}
}
fprintf(stderr, "####\nFinal pass: %u/%u\n", dst, res->used);
res->used = dst;
return res;
}
void init_structures(void)
{
unsigned idx;
for (idx = 0; idx < NRANGE; idx++) {
add_range(&ranges[idx]);
}
}
void list_dmp(FILE *fp, int isupper, struct range *bp)
{
fprintf(fp, "%s", (isupper) ? "Upper" :"Lower" );
for ( ; bp ; bp = (isupper) ? bp->next_hi : bp->next_lo) {
fprintf(fp, " %u:{%s,%s}"
, bp->num , bp->str_lo , bp->str_hi
);
}
fprintf(stdout, "\n");
}
void add_range(struct range *pp)
{
struct treetwo **tpp;
struct range **rpp;
fprintf(stderr, "Inserting range %u->{%s,%s}\n", pp->num, pp->str_lo, pp->str_hi);
/* find low boundary for this interval */
tpp = find_hnd (&root, pp->str_lo);
if (!*tpp) {
fprintf(stderr, "Creating node for %u->%s (low)\n", pp->num, pp->str_lo);
*tpp = malloc(sizeof **tpp);
(*tpp)->list_lo = NULL;
(*tpp)->list_hi = NULL;
(*tpp)->str = pp->str_lo;
}
for (rpp = &(*tpp)->list_lo; *rpp ; rpp = &(*rpp)->next_lo) {;}
*rpp = pp;
fprintf(stderr, "Added range %u->{%s,%s} to treenode(%s)->list_lo\n"
, pp->num, pp->str_lo, pp->str_hi
, (*tpp)->str
);
/* find high boundary */
tpp = find_hnd (&root, pp->str_hi);
if (!*tpp) {
fprintf(stderr, "Creating node for %u->%s (High)\n", pp->num, pp->str_hi);
*tpp = malloc(sizeof **tpp);
(*tpp)->list_lo = NULL;
(*tpp)->list_hi = NULL;
(*tpp)->str = pp->str_hi;
}
for (rpp = &(*tpp)->list_hi; *rpp ; rpp = &(*rpp)->next_hi) {;}
*rpp = pp;
fprintf(stderr, "Added range %u->{%s,%s} to treenode(%s)->list_hi\n"
, pp->num, pp->str_lo, pp->str_hi
, (*tpp)->str
);
}
struct treetwo ** find_hnd(struct treetwo **tpp, char *str)
{
int rc;
for ( ; *tpp; tpp = (rc < 0) ? &(*tpp)->prev : &(*tpp)->next) {
rc = strcmp(str, (*tpp)->str);
if (!rc) break;
}
return tpp;
}
void tree_dmp(FILE *fp, struct treetwo *tp, char *msg, unsigned indent)
{
unsigned uu;
if (!tp) return;
if (!msg) msg = "";
for (uu=0; uu < indent; uu++) { fputc(' ', fp); }
fprintf(fp, "%s:{%s}\n", msg, tp->str);
for (uu=0; uu < indent+1; uu++) { fputc(' ', fp); }
list_dmp(fp , 0, tp->list_lo);
for (uu=0; uu < indent+1; uu++) { fputc(' ', fp); }
list_dmp(fp , 1, tp->list_hi);
tree_dmp(fp, tp->prev, "Prev", indent+2);
tree_dmp(fp, tp->next, "Next", indent+2);
}
int result_resize(struct result *res, unsigned newsize)
{
void *old;
old = res->entries;
res->entries = realloc (res->entries , newsize * sizeof *res->entries);
if (!res->entries) {
res->entries = old; return -1;
}
res->size = newsize;
if (res->used > newsize) res->used = newsize;
return 0;
}
能否請你解釋一下更好的第一段？當範圍以「as」開始（因此「ap」不在其中）時，「蘋果」是如何在範圍2中？此範圍的最大長度爲2，蘋果有5個字符。 – m0skit0 2012-02-17 12:44:23
編輯：真的沒有意義 – UmNyobe 2012-02-17 12:51:28
@UmNyobe我不這麼認爲。我認爲任何字符串開頭的字詞小於'as'的字符都適合範圍[a，as）例如。 「a」，「ace」，「琥珀」，但不是「阿斯」或「阿特伍德」。 – jrok 2012-02-17 12:52:17