Cod sursa(job #1667146)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 28 martie 2016 18:04:39
Problema Aho-Corasick Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.73 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

ifstream in("ahocorasick.in");
ofstream out("ahocorasick.out");

const int TEXT_LEN = 1000005;
const int WORD_LEN = 10005;
const int WCOUNT = 105;

struct trieNode {
   int pathCount;
   int wIndex;
   trieNode *s[26];
   trieNode *failLink, *outLink;

   trieNode() {
      wIndex = 0;
      pathCount = 0;
      memset(s, 0, sizeof(s));
      failLink = outLink = 0;
   }
};

char text[TEXT_LEN];
char word[WORD_LEN];
trieNode *root = new trieNode();
vector<trieNode*> bfsList;
queue<trieNode*> q;
int matchCount[WCOUNT];
int wordId[WCOUNT];

int addWord(char *str, int index) {
   trieNode *t = root;
   for(int i = 0; str[i] != 0; i++) {
      int cur_char = str[i] - 'a';
      if(t->s[cur_char] == 0) {
         t->s[cur_char] = new trieNode();
      }
      t = t->s[cur_char];
   }
   if(!t->wIndex) {
      t->wIndex = index;
   }
   return t->wIndex;
}

void failLinkBfs() {
   root->failLink = root->outLink = root;
   for(int i = 0; i < 26; i++) {
      if(root->s[i] != 0) {
         root->s[i]->failLink = root->s[i]->outLink = root;
         q.push(root->s[i]);
      }
   }
   while(!q.empty()) {
      trieNode *cur = q.front();
      bfsList.push_back(cur);
      q.pop();
      for(int i = 0; i < 26; i++) {
         trieNode *fl = cur->failLink;
         if(cur->s[i] != 0) {
               trieNode *son = cur->s[i];
               while(fl != root && fl->s[i] == 0) {
                  fl = fl->failLink;
               }
               if(fl->s[i] != 0) fl = fl->s[i];
               son->failLink = fl;
               if(son->failLink->wIndex) son->outLink = son->failLink;
               else son->outLink = son->failLink->outLink;

               q.push(cur->s[i]);
         }
      }
   }
}

void findMatches() {
   trieNode *t = root;
   for(int i = 0; text[i] != 0; i++) {
      int cur_char = text[i] - 'a';
      while(t != root && t->s[cur_char] == 0) t = t->failLink;
      if(t->s[cur_char] != 0) t = t->s[cur_char];
      t->pathCount++;
   }
}

void dumpPaths() {
   reverse(begin(bfsList), end(bfsList));
   for(auto t : bfsList) {
      t->outLink->pathCount += t->pathCount;
   }
}

void ahoCorasick() {
   failLinkBfs();
   findMatches();
   dumpPaths();

   for(auto t : bfsList) {
      if(t->wIndex) {
         matchCount[t->wIndex] = t->pathCount;
      }
   }
}

int main() {
   int n, i;

   in >> text >> n;
   for(i = 1; i <= n; i++) {
      in >> word;
      wordId[i] = addWord(word, i);
   }
   ahoCorasick();
   for(i = 1; i <= n; i++) {
      out << matchCount[wordId[i]] << '\n';
   }
   return 0;
}