Q&A
コンパイラのバージョンはいくつですか？例えば g++ --version を実行すれば表示されます。「環境」によって違うという話が出ているように、私の手元ではGCCのバージョンで現象が違うように見える
以下のような関数を作成します。
パラメータにはvectorを入れています。
C++
1template<typename Param> 2int kmp_match(const vector<Param> txt, const vector<Param> pat){ 3 int pt = 1; 4 int pp = 0; 5 vector<int> skip(1024, 0); 6 7 skip[pt] = 0; 8 while(pat[pt] != '\0'){ 9 if(pat[pt] == pat[pp]) 10 skip[++pt] = ++pp; 11 else if(pp == 0) 12 skip[++pt] =pp; 13 else { 14 pp = skip[pp]; 15 } 16 } 17 18 pt = pp = 0; 19 while(txt[pt] != '\0' && pat[pp] != '\0'){ 20 if(txt[pt] == pat[pp]){ 21 pt++; 22 pp++; 23 } else if(pp == 0) 24 pt++; 25 else 26 pp = skip[pp]; 27 } 28 29 if(pat[pp] == '\0') 30 return pt - pp; 31 32 return -1; 33}
この関数を以下のように２回呼び出します。
C++
1int main(){ 2 int idx, idx2; 3 string ss1; 4 string ss2; 5 vector<char> s1(256, 0); 6 vector<char> s2(256, 0); 7 8 cout << "文字列探査" << endl; 9 cout << "テキスト : "; 10 getline(cin, ss1); 11 s1.assign(ss1.begin(), ss1.end()); 12 13 cout << "パターン : "; 14 getline(cin, ss2); 15 s2.assign(ss2.begin(), ss2.end()); 16 17 idx = kmp_match(s1, s2); 18 idx2 = kmp_match(s1, s2); 19 20 if(idx == -1) 21 cout << "パターンは存在しません。" << endl; 22 else 23 printf("%d文字目にマッチします。\n", idx + 1); 24 25 if(idx2 == -1) 26 cout << "パターンは存在しません。" << endl; 27 else 28 printf("%d文字目にマッチします。\n", idx2 + 1); 29 30 return 0; 31}
そうするとおかしな現象が起こります。
[実行結果]
文字列探査
テキスト : you will make me happy
パターン : make
10文字目にマッチします。
パターンは存在しません。
あえてidxを2つ作成しているのですが・・・
１回目と２回めで動作が異なるんです！！
なぜでしょうか？？
どこがおかしいのか分かりません。
わかる方教えてください。
vectorを使っているからでしょうか？？
gcc linux 64bit です。
g++ (Debian 7.2.0-19) 7.2.0
vectorの参考サイト
手を動かしてさくさく理解する
C++ 動的配列クラス std::vector 入門
回答3件
0
ベストアンサー
VCでは発生しませんでしたが、https://ideone.com/では発生しました。
kmp_matchでtxt, patに\0が入っているのを前提にしているのが間違っています。
vector::assignでstringの内容をvectorにコピーしていますが、\0は含まれません。
ss2なら"make"のm～eまでがコピーされてvector::sizeは4、それ以降は不定です。
１回目はたまたま動いているだけだと思いです。
\0と比較している
pat[pt] != '\0'
といった箇所を
pt < pat.size()
に置き換えればいいと思います。
あとはkmp_matchの呼び出しのたびにvectorがコピーされているのでtxt, patは参照にしましょう。
投稿2018/01/14 10:26
編集2018/01/14 10:28
総合スコア2850
ああ！
やってみます。
コンパイラによっても動作が’違うんですね。
う〜〜〜ん。
効率化のためとあるんですが・・・
参照を使うと効率が上がるんですか？？
stringのほうにはナル文字が入っているんでしょうか？
コンパイラというか、多分ヒープの作りとかメモリの状況によると思います。ほんとにたまたまですね、、、
参照渡しは速度的にはポインタ渡しと同じです。
vectorのコピーがないので効率的です。
あ！なるほど！vectorのコピーがないから効率的なのですね！！
stringの方にもナル文字が含まれていないのでしょうか？？
決まってないはずです。string::endは終端の位置を示しているだけでヌル文字とは限らないです。
c_strが返すchar*はヌル終端すると決まっていますが、内部的に文字列をどう持っているかは実装次第のはずなので。
まぁ、c_strでコピーするのも非効率だし大抵はヌル終端するような実装になっていると思いますけどね。
ただ、それを前提にはできないです。
stringの方もヌル文字とは限らないんですか！
わかりました。
見事にできました。
kmp_match()内を直すのは大変だったので、vectorにヌル文字を追加しました。
ありがとうございました。
> コンパイラによっても動作が’違う
私の手元に GCC 5.4.0 と GCC 6.3.0 があり、5.4.0 ではヌル文字との比較で問題なく動作したが、6.3.0では一度目も二度目もパターンマッチしなかった。
そこで、pt < pat.size() 方式に修正したら6.3.0 で問題無く動作するようになった。そして、strike君のコンパイラは7.2.0。
つまり、5.x から 6.x に変わった時にstring（ヒープ？）の実装に大きな変更があった可能性があると思う。
なるほど！
コンパイラによってもstringが変わるのですね。
コンパイラによって違うのは厄介な問題ですね。
C++が進化しているからかな
Cの文字列はヌル文字終端が絶対なので、C++のstringも、まずはヌル文字終端で実装を始めた、だけどsize()で管理するのが本来の設計だったのだから、ある時点でヌル文字終端を捨てた・・・ようなことを門外漢としては想像する。
たぶん、そこは「実装依存」というものじゃないかな。ヌル文字終端を当てにできる場合があるかもしれないが、C++のstringである以上 size()を使えばどのバージョンでも正しく動作する、ということではないか。
0
できるだけ変えないように直してみました。
バグは'\0'の問題なのでs1やs2に'\0'をpush_backすれば直るでしょうけれど、
それ以前の問題として文字列をvectorにコピーする必要性がなさそうにみえます。
C++
1#include <vector> 2#include <string> 3#include <iostream> 4 5using namespace std; 6 7template<typename T> 8int kmp_match(const T& txt, const T& pat) { 9 int pt = 1; 10 int pp = 0; 11 12 const int pt_end = static_cast<int>(txt.length()); 13 const int pp_end = static_cast<int>(pat.length()); 14 if (pt_end < pp_end) return -1; 15 if (pp_end == 0) return 0; 16 vector<int> skip(pp_end + 1, 0); 17 18 skip[pt] = 0; 19 while (pt < pp_end) { 20 if (pat[pt] == pat[pp]) 21 skip[++pt] = ++pp; 22 else if (pp == 0) 23 skip[++pt] = pp; 24 else 25 pp = skip[pp]; 26 } 27 28 pt = pp = 0; 29 while (pt < pt_end && pp < pp_end) { 30 if (txt[pt] == pat[pp]) { 31 pt++; 32 pp++; 33 } else if (pp == 0) 34 pt++; 35 else 36 pp = skip[pp]; 37 } 38 39 if (pp == pp_end) 40 return pt - pp; 41 42 return -1; 43} 44 45int main() { 46 int idx, idx2; 47 string ss1; 48 string ss2; 49 50 cout << "文字列探査" << endl; 51 cout << "テキスト : "; 52 getline(cin, ss1); 53 //ss1 = "abaababbba"; 54 55 cout << "パターン : "; 56 getline(cin, ss2); 57 //ss2 = "abb"; 58 59 idx = kmp_match(ss1, ss2); 60 idx2 = kmp_match(ss1, ss2); 61 62 if (idx == -1) 63 cout << "パターンは存在しません。" << endl; 64 else 65 printf("%d文字目にマッチします。\n", idx + 1); 66 67 if (idx2 == -1) 68 cout << "パターンは存在しません。" << endl; 69 else 70 printf("%d文字目にマッチします。\n", idx2 + 1); 71 72 return 0; 73}
投稿2018/01/14 11:34
編集2018/01/14 12:46
総合スコア88
やはり、ヌル文字の問題のようですね。
関数の中でvector に変換しているのですね！
こちらの方が良さそうですね。
再度作り直します。
ありがとうございます。
> 関数の中でvector に変換しているのですね！
してません。
std::stringクラスにはoperator[]が定義されているので、
std::string s = "abc"; if (s[0] == 'a') …
のような書き方も問題なくできます。
[]が使いたいだけならばvectorに入れる必要はないということです。
ただし文字列の範囲外にならないように先に長さを調べておく必要はあります。
ああ。
すいません。していませんでしたね。
0
こんばんは。
上がっているソースをコピーして動かして見たところ、
現象が確認できませんでした。
実行環境：MacOSX 10.13.2
gcc 4.2.1
実行ソース
C++
1#include <string> 2#include <iostream> 3#include <vector> 4 5using namespace std; 6 7template<typename Param> 8int kmp_match(const vector<Param> txt, const vector<Param> pat){ 9 int pt = 1; 10 int pp = 0; 11 vector<int> skip(1024, 0); 12 13 skip[pt] = 0; 14 while(pat[pt] != '\0'){ 15 if(pat[pt] == pat[pp]) 16 skip[++pt] = ++pp; 17 else if(pp == 0) 18 skip[++pt] =pp; 19 else { 20 pp = skip[pp]; 21 } 22 } 23 24 pt = pp = 0; 25 while(txt[pt] != '\0' && pat[pp] != '\0'){ 26 if(txt[pt] == pat[pp]){ 27 pt++; 28 pp++; 29 } else if(pp == 0) 30 pt++; 31 else 32 pp = skip[pp]; 33 } 34 35 if(pat[pp] == '\0') 36 return pt - pp; 37 38 return -1; 39} 40 41int main(int argc, char **argv) { 42 int idx, idx2; 43 string ss1; 44 string ss2; 45 vector<char> s1(256, 0); 46 vector<char> s2(256, 0); 47 48 cout << "文字列探査" << endl; 49 cout << "テキスト : "; 50 getline(cin, ss1); 51 s1.assign(ss1.begin(), ss1.end()); 52 53 cout << "パターン : "; 54 getline(cin, ss2); 55 s2.assign(ss2.begin(), ss2.end()); 56 57 idx = kmp_match(s1, s2); 58 idx2 = kmp_match(s1, s2); 59 60 if(idx == -1) 61 cout << "パターンは存在しません。" << endl; 62 else 63 printf("%d文字目にマッチします。\n", idx + 1); 64 65 if(idx2 == -1) 66 cout << "パターンは存在しません。" << endl; 67 else 68 printf("%d文字目にマッチします。\n", idx2 + 1); 69 70 return 0; 71} 72
実行結果
実行環境の違いと思いますので、デバッグモードで関数内の変数値を調査するしかないかと思います。
投稿2018/01/14 10:20
総合スコア125
あら？
変ですね・・・
プログラムの方には問題がないんですかね？？
今、ファイルを新しく作り直してみましたが・・・
私の環境だとダメですね。
おかしいぃ！
あなたの回答
tips
プレビュー
