DNA

DNA.cpp

#include<queue>
#include<cstdio>
#include<cstring>
#include<cstdlib>

using namespace std;

struct node{
  node *nodes[4];
  int exists;
  node *failure;
};

node* create_node(){
  node *n;
  for(int i=0;i<4;i++) n->nodes[i] = NULL;
  n->exists = false;
  return n;
}

node *root;

void add(int s[],int l){
  node *x = root;
  int c;
  for(int i=0;i<l;i++){
    c = s[i];
    if(x->nodes[c] == NULL) x->nodes[c] = create_node();
    x = x->nodes[c];
  }
  x->exists = true;
}

void mk_failures(){
  queue<node> q;
  q.push(*root);
  while(!q.empty()){
    node x = q.front();q.pop();
    for(int i=0;i<4;i++){
      if(x.nodes[i]!=NULL){
        node *next = x.failure;
        while(1){
          if(next->nodes[i]!=NULL){
            x.nodes[i]->failure = next->nodes[i];
            break;
          }else if(next == root){
            break;
          }else {
            next = next->nodes[i]->failure;
          }
        }
        q.push(*(x.nodes[i]));
      }
    }
  }
}

void init(){
  root = create_node();
  root->failure = root;
  mk_failures();
}

int count(int s[],int l){
  node *x = root;
  int count = 1;
  int k;
  for(int i=0;i<l;i++){
    k = s[i];
    if(x->nodes[k]==NULL){
      x = x->failure;
      count++;
    }else {
      x = x->nodes[k];
    }
  }
  return count;
}

int* trans(char s[]){
  int l=strlen(s);
  int *r = (int*)malloc(sizeof(int)*l);
  for(int i=0;i<l;i++){
    switch(s[i]){
    case 'A':
      r[i] = 0;
      break;
    case 'T':
      r[i] = 1;
      break;
    case 'G':
      r[i] = 2;
      break;
    case 'C':
      r[i] = 3;
      break;
    }
  }
  return r;
}

main(){
  init();

  int n;
  scanf("%d",&n);

  char s[150001];
  scanf(" %s ",s);
  int *t = trans(s);

  for(int i=0;i<n;i++){
    char k[21];
    scanf(" %s ",s);
    int l = strlen(k);
    int *r = trans(k);
    add(r,l);
  }

  printf("%d\n", count(t,strlen(s)));
}