leftOverlaps() [1/2]

auto SuffixTree::leftOverlaps	(	const Word &	w,
		std::vector< std::pair< int, int > > &	output,
		bool	avoidLast = false ) const->void

Definition at line 595 of file SuffixTree.cpp.

{
  auto tmpNode = mRoot;
  auto tmpLabel = w;
  auto match = findMatch(tmpNode,tmpLabel);
  auto f = std::get<0>(match);
  auto pre = std::get<1>(match);
  int patternNum = -1;
  while (f != nullptr && pre == Word(f->arcLabel()))
    {
      // in this case, the prefix found matches the arc label, so we move down
      // the tree
      tmpNode = f;
      tmpLabel = suffix(tmpLabel,pre.size());
      // after we move down add all children of tmpNode that are suffix leaves to leftOverlaps
      // as long as tmpNode is not the root
      for (auto i = tmpNode->childrenBegin(); i != tmpNode->childrenEnd(); ++i)
        {
          if (i->second->isLeaf() && !i->second->isFullPattern())
            {
              patternNum = i->second->getPatternNumber();
              if (!(avoidLast && patternNum == mMonomials.size()-1))
                output.push_back(std::make_pair(patternNum,
                                                 mMonomials[patternNum].size()-tmpNode->label().size()));
            }
        }
      match = findMatch(tmpNode,tmpLabel);
      f = std::get<0>(match);
      pre = std::get<1>(match);
     }
  // At this point, if pre != {} then there is a common prefix to a child, but
  // the label is not a full match to s.  In this case, we add
  // the unique suffix leaf that shares a prefix to our list,
  // as long as it is not a full pattern
  if (pre.size() != 0 && !f->isFullPattern())
    {
      patternNum = f->getPatternNumber();
      if (!(avoidLast && patternNum == mMonomials.size()-1))
        output.push_back(std::make_pair(patternNum,mMonomials[patternNum].size()-pre.size()));
    }
  return;
}

References findMatch(), mMonomials, mRoot, and suffix().