3

我正在用 C++ 实现一个后缀 trie。构造函数的实现Trie如下所示。

#include <iostream>
#include <cstring>
#include "Trie.hpp"
using namespace std;

Trie::Trie(string T){   
    T += "#";                           //terminating character     
    this->T = T;

    nodes.reserve(T.length() * (T.length() + 1) / 2);   //The number of nodes is bounded above by n(n+1)/2. The reserve prevents reallocation (http://stackoverflow.com/questions/41557421/vectors-and-pointers/41557463) 

    vector<string> suffix;              //vector of suffixes
    for(unsigned int i = 0; i < T.length(); i++)
        suffix.push_back(T.substr(i, T.length()-i));

    //Create the Root, and start from it
    nodes.push_back(Node(""));          //root has blank label
    Node* currentNode = &nodes[0];

    //While there are words in the array of suffixes
    while(!suffix.empty()){

        //If the character under consideration already has an edge, then this will be its index. Otherwise, it's -1.
        int edgeIndex = currentNode->childLoc(suffix[0].at(0));     

        //If there is no such edge, add the rest of the word
        if(edgeIndex == -1){
            addWord(currentNode, suffix[0]);                //add rest of word
            suffix.erase(suffix.begin());                   //erase the suffix from the suffix vector
        }

        //if there is
        else{
            currentNode = (currentNode->getEdge(edgeIndex))->getTo();       //current Node is the next Node
            suffix[0] = suffix[0].substr(1, suffix[0].length());            //remove first character
        }           
    }   
}

//This function adds the rest of a word
void Trie::addWord(Node* parent, string word){  
    for(unsigned int i = 0; i < word.length(); i++){                //For each remaining letter
        nodes.push_back(Node(parent->getLabel()+word.at(i)));       //Add a node with label of parent + label of edge
        Edge e(word.at(i), parent, &nodes.back());                  //Create an edge joining the parent to the node we just added
        parent->addEdge(e);                                         //Join the two with this edge   
    }
}

我正在使用两种数据结构，Node它们Edge有一些你所期望的 getter 和 setter 以及属性。该方法childLoc()返回表示给定字符的边（如果存在）的位置。

代码编译得很好，但由于某种原因，我在运行时收到此错误：

terminate called after throwing an instance of 'std::out_of_range'
  what():  basic_string::at: __n (which is 0) >= this->size() (which is 0)
Aborted (core dumped)

有人告诉我这个错误意味着我正在访问一个空字符串的第一个字符，但我看不到代码中发生这种情况的位置。

4

1 回答 1

0

我看到两个可能负责的代码部分std::out_of_range：

第一：下面的表达式可能会在 position 访问一个空字符串0。这可能会发生（如第二部分所示），您收缩包含在suffix-vector 中的字符串：

int edgeIndex = currentNode->childLoc(suffix[0].at(0));

其次，您对suffix-vector 中的条目进行操作，但存在字符串较短的风险：

suffix[0] = suffix[0].substr(1, suffix[0].length());

如果第一个操作数（即-argument）超过数组长度（参见string::substr ），操作substr也会产生：std::out_of_rangepos

pos：要作为子字符串复制的第一个字符的位置。如果这等于字符串长度，则该函数返回一个空字符串。如果这大于字符串长度，则抛出 out_of_range。注意：第一个字符由值 0（不是 1）表示。

为了找出这些表达式中的哪一个实际上是导致异常的原因，我建议咨询您的调试器:-)

于 2017-01-09T23:02:07.690 回答