找到流中的单词？

Question

给定无限的字符流和字符串列表L，创建一个函数，在处理流时识别L中的单词时调用外部API。

示例： L = [ “OK”， “测试”， “一个”， “尝试”， “尝试”]

流= A，B，C，O，K，d，E， F，T，R，Y，I，N，G .............

到外部API的调用会发生当遇到数 'k'，再次当 'y' 的遇到，并再次在'g'。

我的想法： 创建索引树淘汰之列，并为您的线性时间流中读取导航节点。但是如果你只是简单地使用trie search就会有bug。

假设你有话“abxyz”和“XYW”和你输入“abxyw”。在这种情况下，你可以不承认“XYW”与线索。

那么搜索应该作如下修改：

让我们上面使用情况“abxyw”。我们开始搜索，我们发现我们有所有的元素，直到'x'。此刻你“X”你有两个选择：

1. 检查当前元素等于特里的头，如果它等于特里的头，然后调用递归搜索。

2. 继续直到当前单词结束。在这种情况下，对于给定的输入，它将返回false，但对于我们在第1点开始的递归搜索，它将返回true。

下面是我修改过的搜索，但我认为它有缺陷，可以改进。有什么建议么？

#define SIZE 26 
struct tri{ 
    int complete; 
    struct tri *child[SIZE]; 
}; 

void insert(char *c, struct tri **t) 
{ 
    struct tri *current = *t; 
    while(*c != '\0') 
    { 
     int i; 
     int letter = *c - 'a'; 
     if(current->child[letter] == NULL) { 
      current->child[letter] = malloc(sizeof(*current)); 
      memset(current->child[letter], 0, sizeof(struct tri)); 
     } 
     current = current->child[letter]; 
     c++; 
    } 
    current->complete = 1; 
} 

struct tri *t; 
int flag = 0; 
int found(char *c, struct tri *tt) 
{ 
    struct tri *current = tt; 

    if (current == NULL) 
     return 0; 
    while(*c != '\0') 
    { 
     int i; 
     int letter = *c - 'a'; 
     /* if this is the first char then recurse from begining*/ 
     if (t->child[letter] != NULL) 
      flag = found(c+1, t->child[letter]); 
     if (flag == 1) 
      return 1; 
     if(!flag && current->child[letter] == NULL) { 
      return 0; 
     } 
     current = current->child[letter]; 
     c++; 
    } 
    return current->complete; 
} 

int main() 
{ 
    int i; 
    t = malloc(sizeof(*t)); 
    t->complete = 0; 
    memset(t, 0, sizeof(struct tri)); 

    insert("weathez", &t); 
    insert("eather", &t); 
    insert("weather", &t); 
    (1 ==found("weather", t))?printf("found\n"):printf("not found\n"); 
    return 0; 
} 

Answer 1

你想要做的正是Aho-Corasick algorithm所做的。

你可以看看我的Aho-Corasick实现。这是比赛导向，所以也许不专注于可读性，但我认为这很清楚：

typedef vector<int> VI; 

struct Node { 
    int size; 
    Node *fail, *output; 
    VI id; 
    map<char, Node*> next; 
}; 

typedef pair<Node*, Node*> P; 
typedef map<char, Node*> MCP; 

Node* root; 

inline void init() { 
    root = new Node; 
    root->size = 0; 
    root->output = root->fail = NULL; 
} 

Node* add(string& s, int u, int c = 0, Node* p = root) { 
    if (p == NULL) { 
    p = new Node; 
    p->size = c; 
    p->fail = p->output = NULL; 
    } 
    if (c == s.size()) p->id.push_back(u); 
    else { 
    if (not p->next.count(s[c])) p->next[s[c]] = NULL; 
    p->next[s[c]] = add(s, u, c + 1, p->next[s[c]]); 
    } 
    return p; 
} 

void fill_fail_output() { 
    queue<pair<char, P> > Q; 
    for (MCP::iterator it=root->next.begin(); 
     it!=root->next.end();++it) 
    Q.push(pair<char, P> (it->first, P(root, it->second))); 
    while (not Q.empty()) { 
    Node *pare = Q.front().second.first; 
    Node *fill = Q.front().second.second; 
    char c = Q.front().first; Q.pop(); 
    while (pare != root && !pare->fail->next.count(c)) 
     pare=pare->fail; 
    if (pare == root) fill->fail = root; 
    else fill->fail = pare->fail->next[c]; 
    if (fill->fail->id.size() != 0) 
     fill->output = fill->fail; 
    else fill->output = fill->fail->output; 
    for (MCP::iterator it=fill->next.begin(); 
     it!=fill->next.end();++it) 
     Q.push(pair<char,P>(it->first,P(fill,it->second))); 
    } 
} 

void match(int c, VI& id) { 
    for (int i = 0; i < id.size(); ++i) { 
    cout << "Matching of pattern " << id[i]; 
    cout << " ended at " << c << endl; 
    } 
} 

void search(string& s) { 
    int i = 0, j = 0; 
    Node *p = root, *q; 
    while (j < s.size()) { 
    while (p->next.count(s[j])) { 
     p = p->next[s[j++]]; 
     if (p->id.size() != 0) match(j - 1, p->id); 
     q = p->output; 
     while (q != NULL) { 
     match(j - 1, q->id); 
     q = q->output; 
     } 
    } 
    if (p != root) { 
     p = p->fail; 
     i = j - p->size; 
    } 
    else i = ++j; 
    } 
} 

void erase(Node* p = root) { 
    for (MCP::iterator it = p->next.begin(); 
     it != p->next.end(); ++it) 
    erase(it->second); 
    delete p; 
} 

int main() { 
    init(); 
    int n; 
    cin >> n; 
    for (int i = 0; i < n; ++i) { 
    string s; 
    cin >> s; 
    add(s, i); 
    } 
    fill_fail_output(); 
    string text; 
    cin >> text; 
    search(text); 
    erase(root); 
}