设为首页 加入收藏

TOP

AC自动机简单题(一)
2013-07-23 09:07:18 来源: 作者: 【 】 浏览:534
Tags:动机 简单

    题意:给你n个子串(小写字母, n <= 150, len <= 70),给你个文本串(len <= 10^6), 让你找到在文本串中出现次数最多的子串, 输出最多次数和子串。
    注意:如果出现次数最多的有很多子串,要全部输出,还有n个子串会有重复。
    做法:trie的每个节点用一个vector记录以该节点结尾的单词的标号,find()函数用数组cnt[]下标保存单词标号,值保存次数。然后扫描一下即可。
    [cpp]
    #include <cstdio>
    #include <cstring>
    #include <queue>
    #include <vector>
    #include <algorithm>
    using namespace std;
    const int maxn = 10004 * 51;
    int n;
    char s[1000006], str[155][77];
    int cnt[155];
    struct AC {
    int c[maxn][26], tot, f[maxn];
    vector <int> id[maxn];
    int idx(char c) { return c-'a'; }
    int new_node() {
    memset(c[tot], 0, sizeof(c[tot]));
    id[tot].clear();
    return tot++;
    }
    void init() { tot = 0; new_node(); }
    void insert(char *s, int pos) {
    int i, j, u = 0, n = strlen(s);
    for(i = 0; i < n; i++) {
    int k = idx(s[i]);
    if(!c[u][k]) c[u][k] = new_node();
    u = c[u][k];
    }
    id[u].push_back(pos);
    }
    void getfail() {
    int i, j, u, v;
    queue <int> q;
    f[0] = 0;
    for(i = 0; i < 26; i++) {
    u = c[0][i];
    if(u) { f[u] = 0; q.push(u); }
    }
    while(!q.empty()) {
    u = q.front(); q.pop();
    for(i = 0; i < 26; i++) {
    v = c[u][i];
    if(!v) { c[u][i] = c[f[u]][i]; continue; } // 这行是AC自动机改造: 没改造的是这样的 if(!v) continue;
    j = f[u];
    while(j && !c[j][i]) j = f[j];
    f[v] = c[j][i];
    q.push(v);
    }
    }
    }
    void find(char *s) {
    int i, j, u = 0, n = strlen(s);
    for(i = 0; i < n; i++) {
    int k = idx(s[i]);

   

首页 上一页 1 2 3 下一页 尾页 1/3/3
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇实例看病要排队 优先队列 下一篇用STL的函数生成全排列

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: