aho-corasic

//aho-corasic (find needles in a haystack)
// nasarouf@cs.ubc.ca

//old untested code... but should work :)

/***********************************************************************/
/**      AhoCorasic.h                                                 **/
/**                                                                   **/
/**      (c) 2006                            **/
/**                                                                   **/
/**      Update history:                                              **/
/**        Created:18/01/2006  Mushfiqur Rouf                         **/
/**                                                                   **/
/***********************************************************************/
#ifndef _AHOCORASIC_H_
#define _AHOCORASIC_H_

#include <map>
using namespace std;

template<class ELEM_TYPE,class INDEX_TYPE>
class AhoNode{
    typedef map<ELEM_TYPE,AhoNode*> ahomap;
    ahomap c;
    AhoNode *next,*root;
    INDEX_TYPE index; //positive index

public:
    AhoNode(AhoNode*);
    AhoNode();
    ~AhoNode();
    void clear();
    void build();
    void addPattern(ELEM_TYPE* pat, INDEX_TYPE index);
    int search(ELEM_TYPE *s, vector<INDEX_TYPE> &matchlist);

private:
    void build0();

};

#endif //_AHOCORASIC_H_


/***********************************************************************/
/**      AhoCorasic.cpp                                               **/
/**                                                                   **/
/**      (c) 2006                            **/
/**                                                                   **/
/**      Update history:                                              **/
/**        Created:18/01/2006  Mushfiqur Rouf                         **/
/**                                                                   **/
/***********************************************************************/
#include "StdAfx.h"
#include "AhoCorasic.h"
#include <map>
using namespace std;

template<class ELEM_TYPE,class INDEX_TYPE>
AhoNode<ELEM_TYPE,INDEX_TYPE>::AhoNode(AhoNode<ELEM_TYPE,INDEX_TYPE>* ahoNode=NULL){
    if (ahoNode==NULL)
            root=this;
    else
            root=ahoNode;
    next=root;
    index=0;
}

template<class ELEM_TYPE,class INDEX_TYPE>
AhoNode<ELEM_TYPE,INDEX_TYPE>::~AhoNode(){
    clear();
}

template<class ELEM_TYPE,class INDEX_TYPE>
void AhoNode<ELEM_TYPE,INDEX_TYPE>::clear(){
    ahomap::iterator i;
    for (i=c.begin(); i!=c.end(); i++)
            delete((AhoNode<ELEM_TYPE,INDEX_TYPE>*)((*i).second));
    c.clear();
    next=root;
}

template<class ELEM_TYPE,class INDEX_TYPE>
void AhoNode<ELEM_TYPE,INDEX_TYPE>::addPattern(ELEM_TYPE *pat, INDEX_TYPE index){
    int i;
    AhoNode *ahoNode=root;
    for (i=0; pat[i]; i++){
            if (ahoNode->c.find(pat[i])==ahoNode->c.end())
                    ahoNode->c[pat[i]]=new AhoNode(root);
            ahoNode=ahoNode->c[pat[i]];
    }
    ahoNode->index=index;
}

template<class ELEM_TYPE,class INDEX_TYPE>
void AhoNode<ELEM_TYPE,INDEX_TYPE>::build0(){
    ahomap::iterator i;
    ELEM_TYPE key;
    AhoNode<ELEM_TYPE,INDEX_TYPE> *p,*child;
    for (i=c.begin(); i!=c.end(); i++){
            key=(*i).first;
            child=p=(*i).second;
            while(p && p->c.find(key)!=p->c.end())
                    p=p->next;
            if (p==NULL)
                    child->next=root;
            else
                    child->next=p->c[key];
            child->build();
    }
}

template<class ELEM_TYPE,class INDEX_TYPE>
void AhoNode<ELEM_TYPE,INDEX_TYPE>::build(){
    ahomap::iterator i;
    ELEM_TYPE key;
    AhoNode<ELEM_TYPE,INDEX_TYPE> *p,*child;
    for (i=c.begin(); i!=c.end(); i++){
            key=(*i).first;
            child=p=(*i).second;
            child->next=root;
            child->build();
    }
}

template<class ELEM_TYPE,class INDEX_TYPE>
int AhoNode<ELEM_TYPE,INDEX_TYPE>::search(ELEM_TYPE *s, vector<INDEX_TYPE> &matchlist){
    int i,res=0;
    ELEM_TYPE k;
    AhoNode<ELEM_TYPE,INDEX_TYPE> *p=root,*q;
    for (; *s; s++){
            k=*s;
            while(p && p->c.find(k)==p->c.end())
                    p=p->next;
            if (p==NULL){
                    p=root;
                    continue;
            }
            p=p->c[k];
            q=p;
            do{
                    if (q->index>0){
                            res++;
                            matchlist.push_back(q->index);
                    }
                    q=q->next;
            }while(q!=NULL);
    }
    return res;
}

/*void print(AhoNode *AhoNode,int lev){
    int i,j;
    for (i=0; i<52; i++){
            if (AhoNode->c[i]==NULL) continue;
            for (j=0; j<lev; j++)
                    printf("   ");
            if (i<26) printf("%c ",'a'+i);
            else printf("%c ",'A'+i-26);
            printf(" - id=%d",(AhoNode->c[i]-AhoNodes));
            if (AhoNode->c[i]->next!=NULL) printf(" next=%d",(AhoNode->c[i]->next-AhoNodes));
            if (AhoNode->c[i]->index) printf(" *%d* ",AhoNode->c[i]->index);
            printf("\n");
            print(AhoNode->c[i],lev+1);
    }
}*/

/*int main(){
    int ts,u,i,j,k;
    ELEM_TYPE pat[1001];
    AhoNode *p,*q;
//    freopen("input.txt","rt",stdin);
//    freopen("output.txt","wt",stdout);
    init();
    scanf("%d",&ts);
    for (u=0; u<ts; u++){
            scanf("%s%d",s,&n);
            nc=0;
            root=newAhoNode();
            root->next=NULL;
            for (i=0; i<n; i++)
                    next[i]=0;
            for (i=0; i<n; i++){
                    scanf("%s",pat);
                    add(pat,i);
                    found[i]=0;
            }
            build0();
            p=root;
            for (i=0; s[i]; i++){
                    k=map[s[i]];
                    while(p && p->c[k]==NULL)
                            p=p->next;
                    if (p==NULL){
                            p=root;
                            continue;
                    }
                    p=p->c[k];
                    q=p;
                    do{
                            if (q->index>0) found[q->index-1]=1;
                            q=q->next;
                    }while(q!=NULL);
                    //else if (p->index>0) found[p->index-1]=1;
            }
            for (i=0; i<n; i++){
                    if (found[i]){
                            j=i;
                            while(next[j]>0){
                                    j=next[j]-1;
                                    found[j]=1;
                            }
                    }
            }
            for (i=0; i<n; i++){
                    if (found[i]) printf("yes\n");
                    else printf("no\n");
            }
            //print(root,0);
    }
    return 0;
}
*/