以下のような関数を作成します。
パラメータには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}
この関数を以下のように2回呼び出します。
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つ作成しているのですが・・・
1回目と2回めで動作が異なるんです!!
なぜでしょうか??
どこがおかしいのか分かりません。
わかる方教えてください。
vectorを使っているからでしょうか??
gcc linux 64bit です。
g++ (Debian 7.2.0-19) 7.2.0
vectorの参考サイト
手を動かしてさくさく理解する
C++ 動的配列クラス std::vector 入門
回答3件
あなたの回答
tips
プレビュー