segmentation faultというエラーを直して、力まかせ法を実装したい。

Question

実現したいこと

力まかせ法による文字列検索を行いたいです。

前提

実行結果がsegmentation faultというエラーが発生します。

発生している問題・エラーメッセージ

segmentation fault

該当のソースコード

#include <stdio.h>
#include <string.h>
#include <limits.h>

char *km_match(char *pat, char *txt)
{
char *pt; char *pp;
int skip[1024];
skip[*pt]=0;
while(pat[*pt] != '\n'){
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] != '\n' && pat[*pp] != '\n'){
if(txt[*pt]==pat[*pp]){
*pt++;
*pp++;
}else if(*pp==0)
*pt++;
else
*pp=skip[*pp];
}
if(pat[*pp]=='\n')
return(txt +*pt-*pp);
return(NULL);
}

### 試したこと

ここに問題に対して試したことを記載してください。

### 補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

バグあったら指摘よろしくです。

#include <stddef.h>

/*
 txt から pat を探し、その位置を返す。
 見つからないときは NULL を返す。 
 */
char* search(const char* pat, char* txt) {
  if ( !pat || !txt ) return NULL;
  while ( *txt != '0' ) {
    // (０文字目から一致しない比較をするのはムダなので)
    // 最初の文字と一致する位置まで進んで
    while ( !*txt && *txt != *pat ) ++txt;
    if ( !*txt ) return NULL;

    // そこから pat と txt が一致するか調べる
    const char* p = pat;
    const char* t = txt;
    while ( *p && *t ) {
      if ( *p != *t ) break;
      ++p;
      ++t;
    }
    if ( !*p ) return txt; // 一致した!
    ++txt;
  }
  return NULL; 
}

// おためし

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main() {
  const char* pat = "abc";
  const char* txts[] = { "ab", "ababab", "abc", "xabc", "xabcd", "abababc", NULL };
  
  for ( const char** p = txts; *p != NULL; ++p ) {
    char* txt = _strdup(*p);
    char* result = search(pat, txt);
    if ( result )
      printf("match(\"%s\", \"%s\")\t= %s + %lld\n", pat, txt, txt, result - txt);
    else
      printf("match(\"%s\", \"%s\") = NULL\n", pat, txt);
    free(txt);    
  }
}

Comments

[sho888]

ありがとうございます。すみません。もう１つあり、この関数の引数はそのままでKMP法を実施する場合はどのように変えればよいですか？教えてください。

Answer 2

C/C++ ではビルドするときの警告レベルを最大にして、まずは警告なしでビルドできるようにするのがお勧めです。また、segmentation falult などでクラッシュする場合は、デバッグビルドして、デバッガ上で実行して問題箇所を見つけましょう。gcc なら gcc -Wall -g ソースファイル名.c などです。

char *pt; char *pp;
int skip[1024];
skip[*pt]=0;

pt が初期化されていないので、skip[*pt] で高確率でクラッシュします。

int pt = 0; ... skip[pt] = 0; とかじゃないですかね。pp も同様。

Comments

[sho888]

課題でchar *pt; char *pp;を使ってkm_matchの関数の引数を変えないという指示で
力まかせ法を実装できるプログラムを作成したいです。

[int32_t]

では、
char* pt = txt;
char* pp = pat;
にして、それ以降は pat txt を使わないように実装するのが出題意図かもしれません。

[int32_t]

あと、「力まかせ法による文字列検索」と言っているのにコードは KMP 法をやろうとしているように見えます。力まかせ法で skip とか不要ですよね。

[sho888]

ありがとうございます。
解決しました。助かりました。

[sho888]

すみません。ＫＭＰ法でした。
KMP法で分かる方教えてください。