質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.61%

  • C++

    3340questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • GCC

    138questions

    GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。

同じ関数を2回呼び出すと動作が変わってしまう

解決済

回答 3

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 359

strike1217

score 552

以下のような関数を作成します。
パラメータにはvectorを入れています。

template<typename Param>
int kmp_match(const vector<Param> txt, const vector<Param> pat){
    int pt = 1;
    int pp = 0;
    vector<int> skip(1024, 0);

    skip[pt] = 0;
    while(pat[pt] != '\0'){
        if(pat[pt] == pat[pp])
            skip[++pt] = ++pp;
        else if(pp == 0)
            skip[++pt] =pp;
        else {
            pp = skip[pp];
        }
    }

    pt = pp = 0;
    while(txt[pt] != '\0' && pat[pp] != '\0'){
        if(txt[pt] == pat[pp]){
            pt++;
            pp++;
        } else if(pp == 0)
            pt++;
        else 
            pp = skip[pp];
    }

    if(pat[pp] == '\0')
        return pt - pp;

    return -1;
}


この関数を以下のように2回呼び出します。

int main(){
    int idx, idx2;
    string ss1;
    string ss2;
    vector<char> s1(256, 0);
    vector<char> s2(256, 0);

    cout << "文字列探査" << endl;
    cout << "テキスト : ";
    getline(cin, ss1);
    s1.assign(ss1.begin(), ss1.end());

    cout << "パターン : ";
    getline(cin, ss2);
    s2.assign(ss2.begin(), ss2.end());

    idx = kmp_match(s1, s2);
    idx2 = kmp_match(s1, s2);

    if(idx == -1)
        cout << "パターンは存在しません。"  << endl;
    else
        printf("%d文字目にマッチします。\n", idx + 1);

    if(idx2 == -1)
        cout << "パターンは存在しません。"  << endl;
    else
        printf("%d文字目にマッチします。\n", idx2 + 1);

    return 0;
}

そうするとおかしな現象が起こります。

[実行結果]
文字列探査
テキスト : 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 入門

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • rubato6809

    2018/01/14 22:01

    コンパイラのバージョンはいくつですか?例えば g++ --version を実行すれば表示されます。「環境」によって違うという話が出ているように、私の手元ではGCCのバージョンで現象が違うように見える

    キャンセル

  • strike1217

    2018/01/14 22:03

    おっと、これは失礼しました。バージョンも載せておきます。

    キャンセル

回答 3

checkベストアンサー

+2

VCでは発生しませんでしたが、https://ideone.com/では発生しました。

kmp_matchでtxt, patに\0が入っているのを前提にしているのが間違っています。
vector::assignでstringの内容をvectorにコピーしていますが、\0は含まれません。
ss2なら"make"のm~eまでがコピーされてvector::sizeは4、それ以降は不定です。
1回目はたまたま動いているだけだと思いです。

\0と比較している

pat[pt] != '\0'

といった箇所を

pt < pat.size()

に置き換えればいいと思います。

あとはkmp_matchの呼び出しのたびにvectorがコピーされているのでtxt, patは参照にしましょう。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/14 19:29

    ああ!
    やってみます。

    コンパイラによっても動作が’違うんですね。
    う〜〜〜ん。

    効率化のためとあるんですが・・・
    参照を使うと効率が上がるんですか??

    キャンセル

  • 2018/01/14 19:36 編集

    stringのほうにはナル文字が入っているんでしょうか?

    キャンセル

  • 2018/01/14 19:36

    コンパイラというか、多分ヒープの作りとかメモリの状況によると思います。ほんとにたまたまですね、、、
    参照渡しは速度的にはポインタ渡しと同じです。
    vectorのコピーがないので効率的です。

    キャンセル

  • 2018/01/14 19:41

    あ!なるほど!vectorのコピーがないから効率的なのですね!!

    stringの方にもナル文字が含まれていないのでしょうか??

    キャンセル

  • 2018/01/14 19:44

    決まってないはずです。string::endは終端の位置を示しているだけでヌル文字とは限らないです。
    c_strが返すchar*はヌル終端すると決まっていますが、内部的に文字列をどう持っているかは実装次第のはずなので。
    まぁ、c_strでコピーするのも非効率だし大抵はヌル終端するような実装になっていると思いますけどね。
    ただ、それを前提にはできないです。

    キャンセル

  • 2018/01/14 19:51

    stringの方もヌル文字とは限らないんですか!

    わかりました。

    キャンセル

  • 2018/01/14 22:02

    見事にできました。

    kmp_match()内を直すのは大変だったので、vectorにヌル文字を追加しました。

    キャンセル

  • 2018/01/14 22:04

    ありがとうございました。

    キャンセル

  • 2018/01/14 22:15 編集

    > コンパイラによっても動作が’違う

    私の手元に 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(ヒープ?)の実装に大きな変更があった可能性があると思う。

    キャンセル

  • 2018/01/14 22:27 編集

    なるほど!
    コンパイラによってもstringが変わるのですね。

    コンパイラによって違うのは厄介な問題ですね。
    C++が進化しているからかな

    キャンセル

  • 2018/01/14 22:42 編集

    Cの文字列はヌル文字終端が絶対なので、C++のstringも、まずはヌル文字終端で実装を始めた、だけどsize()で管理するのが本来の設計だったのだから、ある時点でヌル文字終端を捨てた・・・ようなことを門外漢としては想像する。
    たぶん、そこは「実装依存」というものじゃないかな。ヌル文字終端を当てにできる場合があるかもしれないが、C++のstringである以上 size()を使えばどのバージョンでも正しく動作する、ということではないか。

    キャンセル

+1

こんばんは。

上がっているソースをコピーして動かして見たところ、
現象が確認できませんでした。

実行環境:MacOSX 10.13.2
gcc 4.2.1

実行ソース

#include <string>
#include <iostream>
#include <vector>

using namespace std;

template<typename Param>
int kmp_match(const vector<Param> txt, const vector<Param> pat){
    int pt = 1;
    int pp = 0;
    vector<int> skip(1024, 0);

    skip[pt] = 0;
    while(pat[pt] != '\0'){
        if(pat[pt] == pat[pp])
            skip[++pt] = ++pp;
        else if(pp == 0)
            skip[++pt] =pp;
        else {
            pp = skip[pp];
        }
    }

    pt = pp = 0;
    while(txt[pt] != '\0' && pat[pp] != '\0'){
        if(txt[pt] == pat[pp]){
            pt++;
            pp++;
        } else if(pp == 0)
            pt++;
        else
            pp = skip[pp];
    }

    if(pat[pp] == '\0')
        return pt - pp;

    return -1;
}

int main(int argc, char **argv) {
    int idx, idx2;
    string ss1;
    string ss2;
    vector<char> s1(256, 0);
    vector<char> s2(256, 0);

    cout << "文字列探査" << endl;
    cout << "テキスト : ";
    getline(cin, ss1);
    s1.assign(ss1.begin(), ss1.end());

    cout << "パターン : ";
    getline(cin, ss2);
    s2.assign(ss2.begin(), ss2.end());

    idx = kmp_match(s1, s2);
    idx2 = kmp_match(s1, s2);

    if(idx == -1)
        cout << "パターンは存在しません。"  << endl;
    else
        printf("%d文字目にマッチします。\n", idx + 1);

    if(idx2 == -1)
        cout << "パターンは存在しません。"  << endl;
    else
        printf("%d文字目にマッチします。\n", idx2 + 1);

    return 0;
}

実行結果
実行結果

実行環境の違いと思いますので、デバッグモードで関数内の変数値を調査するしかないかと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/14 19:22

    あら?
    変ですね・・・

    プログラムの方には問題がないんですかね??

    キャンセル

  • 2018/01/14 19:26

    今、ファイルを新しく作り直してみましたが・・・
    私の環境だとダメですね。

    おかしいぃ!

    キャンセル

+1

できるだけ変えないように直してみました。
バグは'\0'の問題なのでs1やs2に'\0'をpush_backすれば直るでしょうけれど、
それ以前の問題として文字列をvectorにコピーする必要性がなさそうにみえます。

#include <vector>
#include <string>
#include <iostream>

using namespace std;

template<typename T>
int kmp_match(const T& txt, const T& pat) {
    int pt = 1;
    int pp = 0;

    const int pt_end = static_cast<int>(txt.length());
    const int pp_end = static_cast<int>(pat.length());
    if (pt_end < pp_end) return -1;
    if (pp_end == 0) return 0;
    vector<int> skip(pp_end + 1, 0);

    skip[pt] = 0;
    while (pt < pp_end) {
        if (pat[pt] == pat[pp])
            skip[++pt] = ++pp;
        else if (pp == 0)
            skip[++pt] = pp;
        else
            pp = skip[pp];
    }

    pt = pp = 0;
    while (pt < pt_end && pp < pp_end) {
        if (txt[pt] == pat[pp]) {
            pt++;
            pp++;
        } else if (pp == 0)
            pt++;
        else
            pp = skip[pp];
    }

    if (pp == pp_end)
        return pt - pp;

    return -1;
}

int main() {
    int idx, idx2;
    string ss1;
    string ss2;

    cout << "文字列探査" << endl;
    cout << "テキスト : ";
    getline(cin, ss1);
    //ss1 = "abaababbba";

    cout << "パターン : ";
    getline(cin, ss2);
    //ss2 = "abb";

    idx = kmp_match(ss1, ss2);
    idx2 = kmp_match(ss1, ss2);

    if (idx == -1)
        cout << "パターンは存在しません。" << endl;
    else
        printf("%d文字目にマッチします。\n", idx + 1);

    if (idx2 == -1)
        cout << "パターンは存在しません。" << endl;
    else
        printf("%d文字目にマッチします。\n", idx2 + 1);

    return 0;
}

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/14 21:53

    やはり、ヌル文字の問題のようですね。

    キャンセル

  • 2018/01/14 21:56

    関数の中でvector に変換しているのですね!
    こちらの方が良さそうですね。

    再度作り直します。
    ありがとうございます。

    キャンセル

  • 2018/01/14 22:37

    > 関数の中でvector に変換しているのですね!
    してません。
    std::stringクラスにはoperator[]が定義されているので、
    std::string s = "abc"; if (s[0] == 'a') …
    のような書き方も問題なくできます。
    []が使いたいだけならばvectorに入れる必要はないということです。
    ただし文字列の範囲外にならないように先に長さを調べておく必要はあります。

    キャンセル

  • 2018/01/14 22:55

    ああ。
    すいません。していませんでしたね。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.61%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3340questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • GCC

    138questions

    GCCはGNU Compiler Collectionの略です。LinuxのC言語コンパイラのデファクトスタンダードであり、数多くの他言語やプラットフォームサポートもします。