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ループを
       調節します。

←解決時は質問者本人がここをチェックしてください。

戻る