当前位置:编程学习 > C/C++ >>

LA 4670 AC自动机简单题

题意:给你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]);  
        //  while(u && !c[u][k]) u = f[u]; // 改造后的AC自动机,这句话不用写  
            u = c[u][k];  
            for(j = u; j; j = f[j]) {  
                for(int k = 0; k < id[j].size(); k++)  
                    cnt[id[j][k]]++;  
            }  
        }   
    }  
}ac;  
int main() {  
    int i, j;    
    while( ~scanf("%d", &n) && n) {  
        ac.init();  
        memset(cnt, 0, sizeof(cnt));  
        for(i = 1; i <= n; i++) {  
            scanf("%s", str[i]);  
            ac.insert(str[i], i);  
        }  
        ac.getfail();  
        scanf("%s", s);  
        ac.find(s);  
        int ans = 0;  
      
        for(i = 1; i <= n; i++)  
            if(ans < cnt[i]) ans = cnt[i];  
        printf("%d\n", ans);  
        for(i = 1; i <= n; i++)  
            if(ans == cnt[i]) puts(str[i]);  
    }  
    return 0;  
}  
 
补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,