HDU2896: Virus Infection

Problem Description: There are N computer viruses and M potential infected websites. Each virus and website can be described as a string. The task is to find which websites are infected by what kinds of viruses and the total number of infected websites with viruses. 

Input Format:
The first line contains one number N.
The next N lines contain strings representing viruses.
The next line contains one number M.
The nxt M lines contain strings representing the websites.

Output Format:
For each website, output the the website id and the virus ids.
The last line contains total number of websites with viruses.

Sample Input:
3
aaa
bbb
ccc
2
aaabbbccc
bbaacc

Sample Output:
web 1: 1 2 3
total: 1

Solution: This is a AC automaton problem. We use the viruses strings to build the Trie tree. For each website, we run the string on the Trie tree. Because the virus string must be a suffix of a prefix of the website string if it is contained in the website string, we can jump on the fail tree to get all suffix to see if current prefix has any suffix that matches the virus string.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
#define inf 0x7f7f7f7f
const int maxn = 100005;
struct Trie{
    int sum,nxt[130],fail,id;
} tree[maxn];
int tot,N,M;
inline int idx(char c){return (int)c;}
void addnode(string s,int id){
    int rt = 0;
    for(int i = 0; i < s.size(); i++){
        int c = idx(s[i]);
        if(!tree[rt].nxt[c]) tree[rt].nxt[c] = ++tot;
        rt = tree[rt].nxt[c];
    }
    tree[rt].sum++;
    tree[rt].id = id;
}
queue<int> q;
void get_fail(){
    for(int i = 0; i <= 128; i++){
        if(tree[0].nxt[i]){
            q.push(tree[0].nxt[i]);
            tree[tree[0].nxt[i]].fail = 0;
        }
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = 0; i <= 128; i++){
            if(tree[u].nxt[i]){
                tree[tree[u].nxt[i]].fail = tree[tree[u].fail].nxt[i];
                q.push(tree[u].nxt[i]);
            }
            else tree[u].nxt[i] = tree[tree[u].fail].nxt[i];
        }
    }
}

int solve(string s,int webcnt){
    int rt = 0;
    int sum = 0;
    vector<int> v;
    for(int i = 0; i < s.size(); i++){
        if(sum == 3) break;
        int c = idx(s[i]);
        while(!tree[rt].nxt[c] && rt) rt = tree[rt].fail;
        rt = tree[rt].nxt[c];
        int cur = rt;
        while(cur){
            if(tree[cur].sum){
                v.push_back(tree[cur].id);
                sum++;
            }
            cur = tree[cur].fail;
        }
    }
    if(!sum) return 0;
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    cout<<"web "<<webcnt<<":";
    for(int i = 0; i < v.size(); i++) cout<<" "<<v[i];
    cout<<endl;
    return (webcnt != 0);
}
string s;
int main(){
    FAST_IO
    int N;
    cin>>N;
    for(int i = 1; i <= N; i++){
        cin>>s;
        addnode(s,i);
    }
    get_fail();
    cin>>M;
    int ans = 0;
    for(int i = 1; i <= M; i++){
        cin>>s;
        ans += solve(s,i);
    }
    cout<<"total: "<<ans<<endl;
    return 0;
}