概要

文字列探索アルゴリズム。

ある文字列 \(T\) について、 \(N\) 個の文字列 \(s_1, s_2, ..., s_N\) の中からマッチする(最長の)文字列を線形に探索することができる。

計算量

\(O(|T| + \sum_i |s_i|)\)

実装

Python版 がベース

#include<string>
#include<queue>
using namespace std;

#define NN 30
 
struct TrieNode {
  TrieNode(int size) : sz(size), cnt(0) {
    for(int i = 0; i < NN; ++i) next[i] = nullptr;
    suffix = nullptr;
  }
  TrieNode *next[NN];
  TrieNode *suffix;
  int sz, cnt;
};
 
TrieNode *root = new TrieNode(0);
 
void add(string s) {
  TrieNode *node = root;
  for(int i = 0; i < s.length(); ++i) {
    int code = s[i] - 'a';
    if(!node->next[code]) {
      node = node->next[code] = new TrieNode(node->sz + 1);
    } else {
      node = node->next[code];
    }
  }
  node->cnt = 1;
}
 
void suffix() {
  queue<TrieNode*> que;
  que.push(root);
  while(!que.empty()) {
    TrieNode* v = que.front(); que.pop();
    for(int i = 0; i< NN; ++i) {
      if(v->next[i] && v->sz < v->next[i]->sz) {
        if(v->suffix) {
          v->next[i]->suffix = v->suffix->next[i];
        } else {
          v->next[i]->suffix = root;
        }
        que.push(v->next[i]);
      } else {
        if(v->suffix) {
          v->next[i] = v->suffix->next[i];
        } else {
          if(root->next[i]) {
            v->next[i] = root->next[i];
          } else {
            v->next[i] = root;
          }
        }
      }
    }
  }
  root->suffix = root;
}

Verified

  • AtCoder: "JAG Practice Contest for ACM-ICPC Asia Regional 2017 - H問題: Separate String": source (C++14, 396ms)

戻る