0

2 つの文字列間の最長の共通サブシーケンスを決定するプログラムを作成しました。LCSLength()ハードコードされた小さなテストケースで関数をテストしたところ、正しい値が返されました。

現在、ファイルから文字列を読み取って比較していますが、プログラムでセグメンテーション違反が発生します。コードは次のとおりです。

#include <iostream>
#include <string>
#include <vector>
#include <fstream>
using namespace std;

int LCSLength(string X,string Y);

int main()
{
    ifstream inData("sequences.dat");
    vector<string> lines(1);
    string line;
    int LCS;

    while (getline(inData,line)) 
    {
        if (line.empty()) 
            lines.push_back("");
        else 
            lines.back() += line;
    }

    LCS = LCSLength(lines[0],lines[1]);
    cout << "The LCS is: " << LCS << endl;
    return 0;
}


int LCSLength(string X,string Y)
{
    int m = X.size();
    int n = Y.size();
    int L[m+1][n+1];
    for(int i=0; i<=m; i++)
    {
        for(int j=0; j<=n; j++)
        {
            if(i==0 || j==0)
                L[i][j] = 0;
            else if(X[i-1]==Y[j-1])
                L[i][j] = L[i-1][j-1]+1;
            else
                L[i][j] = max(L[i-1][j],L[i][j-1]);
        }
    }
    return L[m][n];
}

-pedantic -ansi を使用してコンパイルすると、次のエラーが発生します: In function LCSLength(std::string, std::string): ISO C++ forbids variable size array 'L'.

Valgrind を使用してコンパイルしましたが、生成されたエラーは次のとおりです。

==15183== LEAK SUMMARY:
==15183==    definitely lost: 8,624 bytes in 14 blocks
==15183==    indirectly lost: 1,168 bytes in 5 blocks
==15183==      possibly lost: 5,518 bytes in 58 blocks
==15183==    still reachable: 44,925 bytes in 278 blocks
==15183==         suppressed: 0 bytes in 0 blocks
==15183== Reachable blocks (those to which a pointer was found) are not shown.
==15183== To see them, rerun with: --leak-check=full --show-reachable=yes
==15183== 
==15183== ERROR SUMMARY: 23 errors from 23 contexts (suppressed: 0 from 0)
==15183== 
==15183== 1 errors in context 1 of 23:
==15183== Invalid read of size 4
==15183==    at 0x38326: std::string::_Rep::_M_grab(std::allocator<char> const&, std::allocator<char> const&) (in /usr/lib/libstdc++.6.0.9.dylib)
==15183==    by 0x388EF: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) (in /usr/lib/libstdc++.6.0.9.dylib)
==15183==    by 0x100001AAE: main (firstt.cpp:23)
==15183==  Address 0xfffffffffffffff8 is not stack'd, malloc'd or (recently) free'd
==15183== 
==15183== 
==15183== 1 errors in context 2 of 23:
==15183== Invalid read of size 8
==15183==    at 0x388DC: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::string const&) (in /usr/lib/libstdc++.6.0.9.dylib)
==15183==    by 0x100001AAE: main (firstt.cpp:23)
==15183==  Address 0x100023d28 is 0 bytes after a block of size 8 alloc'd
==15183==    at 0x5237: malloc (in /usr/local/Cellar/valgrind/3.8.1/lib/valgrind/vgpreload_memcheck-amd64-darwin.so)
==15183==    by 0x4B346: operator new(unsigned long) (in /usr/lib/libstdc++.6.0.9.dylib)
==15183==    by 0x100002DFE: __gnu_cxx::new_allocator<std::string>::allocate(unsigned long, void const*) (new_allocator.h:91)
==15183==    by 0x100002E42: std::_Vector_base<std::string, std::allocator<std::string> >::_M_allocate(unsigned long) (stl_vector.h:131)
==15183==    by 0x100002E9D: std::_Vector_base<std::string, std::allocator<std::string> >::_Vector_base(unsigned long, std::allocator<std::string> const&) (stl_vector.h:116)
==15183==    by 0x1000030E4: std::vector<std::string, std::allocator<std::string> >::vector(unsigned long, std::string const&, std::allocator<std::string> const&) (stl_vector.h:215)
==15183==    by 0x1000017D9: main (firstt.cpp:11)
==15183== 
==15183== ERROR SUMMARY: 23 errors from 23 contexts (suppressed: 0 from 0)
Segmentation fault: 11

テスト ファイルには 2 行のシーケンスがあります。I をチェックするlines.size()と、2 が返されます。Icout << lines[0]とcout << lines[1]と 正しい文字列も表示されます。

誰でもこれを理解するのを手伝ってもらえますか? ありがとう。

4

2 に答える 2

0

lines[0]while ループを抜けた後、との両方が存在することを確認しましたlines[1]か? これは、入力ファイルに少なくとも 1 行の空行がある場合 (およびそのように認識された場合) にのみ発生します。

mainValgrind によると (その出力を読んでください!) - からではなく、内部 (11 行目または 23 行目)で何か間違ったことをしていますLCSLength。

于 2012-12-05T13:02:12.403 に答える
0

ベクトルには常に 1 つの要素が含まれてlinesいるため、インデックス 1 でアクセスすると UB が発生します

LCS = LCSLength(lines[0],lines[1]);
                          here ^
于 2012-12-05T12:59:49.580 に答える