strncmp(), Segmentation fault (ID:68056)

名前

ホームページ(ブログ、Twitterなど)のURL (省略可)

本文 strncmp(a, b, 1) は strcmp(a, b) と書くべきでした。 この点は誤解をまねいてしまったと思います。すみません。 ただ、ポインタ集合をソートしているというのは誤解だと思いますので、 その点は説明させてください。 上のプログラムで行っていたのは、Suffix Array の構築です。 接尾辞配列 - Wikipedia http://ja.wikipedia.org/wiki/%E6%8E%A5%E5%B0%BE%E8%BE%9E%E9%85%8D%E5%88%97 vector<char*> のようにchar*を格納しているのは、Cの文字列が リスト構造(リンクリスト)と等価だからです。 たとえば、文字列"aabbabbbb"があるとき、この文字列の （連続する）部分文字列のうち、一番長い重複文字列を求めるとき、 Suffix Arrayとchar*の組み合わせがとても有効です(文字列がとても大きい場合)。 (正確にはchar*ではなくてリンク構造(リンクリスト)であればよい) bool cmp(const char* a, const char* b) { return strcmp(a, b) < 0; } vector<char*> v; char* s = "aabbabbbb"; for (int i=0; i < strlen(s); i++) // (**1**) v.push_back(s + i); sort(v.begin(), v.end(), cmp); ソートするとvの中身は次のようになります: v[0] = aabbabbbb v[1] = abbabbbb v[2] = abbbb v[3] = b v[4] = babbbb v[5] = bb v[6] = bbabbbb v[7] = bbb v[8] = bbbb 一番長い重複文字列を調べるには、ソート後にO(strlen(v[i]) + v.size())で分かります。 文字列の先頭部分を比較するだけで良いからです。 この場合abb、またはbbbです。 もし文字列"aabbabbbb"の中で、(連続する)「長さが n である」部分文字列のうち、 もっとも出現頻度が高い文字列を求めたいとき、cmp()のなかでstrcmpを使うのは 効率が悪いのでstrncmpを使うべきです。なぜなら、「長さが n」であるので、 文字列末尾まで調べる必要はなく、 先頭から n 文字まで比較するだけでソートを行えるからです。(補足*1) (これがぼくが最初の質問でstrcmpではなく、strncmpを使った理由です。 ただ、strncmpの引数に 1 を指定してしまって、 文字の比較と誤解させるようなコードを書いてしまったことは申し訳なかったです。 すみません) 補足*1 たとえば、「長さが 3」の場合、先頭から3文字調べるだけで十分です。 このとき strlen(v[i]) が 3 以上になるように (**1**)のforループを 調節します。