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   
    }
}

私は 2 つのデータ構造を使用しています。これらには、予想されるゲッターとセッター、およびプロパティがいくつかありますNode。Edgeこのメソッド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

の原因となる可能性のある 2 つのコード部分がありますstd::out_of_range。

最初: 次の式は、位置 の空の文字列にアクセスする可能性があります0。これは (2 番目の部分で示されているように) suffix-vectorに含まれる文字列を縮小すると発生する可能性があります。

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

suffix次に、 -vectorのエントリを操作すると、文字列が短くなるリスクがあります。

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

第 1 オペランド (つまり-argument) が配列の長さを超えた場合substrにも演算が行われます ( string::substrを参照):std::out_of_rangepos

pos: 部分文字列としてコピーされる最初の文字の位置。これが文字列の長さと等しい場合、関数は空の文字列を返します。これが文字列の長さより大きい場合、out_of_range をスローします。注: 最初の文字は 0 (1 ではない) の値で示されます。

これらの式のどれが実際に例外の原因であるかを見つけるために、デバッガーに相談することをお勧めします:-)

于 2017-01-09T23:02:07.690 に答える