insertStepC()

auto SuffixTree::insertStepC	(	SuffixTreeNode *	v,
		SuffixTreeNode *	x,
		const Word &	beta,
		const Word &	s,
		bool	isFullPattern )->InsertType

Definition at line 223 of file SuffixTree.cpp.

{
  // Carries out step C in the algorithm.  This amounts to computing (and building,
  // if necessary) the suffix link of v.  This function can call the Step D code
  // as well (see the algorithm in the paper by Amir, et.al.)
  auto iwType = extendedLocus(x, beta);
  auto f = std::get<0>(iwType);
  auto betaHat = std::get<1>(iwType);
  if (f->arcLabel().size() == betaHat.size())
    {
      // in this case, f is in fact the locus of beta
      v->setSuffixLink(f);
      return insertStepD(f,suffix(s,f->label().size()),isFullPattern);
    }
  // in this case, f is the extended locus of beta.  We need to split
  // the arc from f to its parent and insert a node d and a child
  // w which will be the locus of beta
  auto d = splitArc(f,betaHat);
  // update pattern leaf count of d
  d->setPatternLeafCount(f->patternLeafCount());
  d->addToPatternLeafCount(isFullPattern);
  d->addToPatternLeafCount(f->isFullPattern());
  // add in the locus of s
  auto w = new SuffixTreeNode(d,suffix(s,d->label().size()),isFullPattern);
  // set the suffix link of v to d
  v->setSuffixLink(d);
  if (w->label().size() == 1)
    return std::make_tuple(d,f,w);
  else
    return std::make_tuple(d,nullptr,w);
}

References extendedLocus(), insertStepD(), s, splitArc(), suffix(), and x.

Referenced by insert(), and insertWorker().