合計 昨日 今日

ボイヤー・ムーア法について

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: hnkto
[URL]
ぴよぴよ(413 ポイント)
Date: 2017年11月27日(月) 19:30
No: 1
(OFFLINE)

 ボイヤー・ムーア法について

今、大学のアルゴリズムの授業でbm法やkmp法をやっているところなのですが、bm法のプログラムを書いてみたところうまく動いてくれません。どこがおかしいのでしょうか?

やりたいことは、入力された文字列によってスキップ表を作り、それにより文字列がある位置を表示することです。

コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include<stdio.h>
#include<string.h>
 
void compute_g(char [],int []);
void bm(char [],char []);
void compute_h(char[]);
int max(int a, int b);
int min(int a, int b);
 
int main(void)
{
    char t[30];
    char p[10];
   
    strcpy(t,"ababdababccbdccabcadb");
   
    printf("テキスト:%s\n",t);
   
    printf("探したい文字列を入力してください:");
    scanf("%s",p);
   
    bm(t,p);
   
    return 0;
}
 
void bm(char t[],char p[])
{
    int m = strlen(p);
    int n = strlen(t);
    int i = m - 1;
    int j = m - 1;
    int flag=  0;
    int g[256];
    int h[m];
   
    compute_g(p,g);
    compute_h(p);
   
    while(i >= 0 && j < n && j >= 0){
        if(p[i] == t[j]){
            i--;
            j--;
        }else{
            j = j + max(g[(int)t[j]],h[i]);
            i = m - 1;
        }
            if(i == -1){
            printf("Pattern has found at %d.\n",j+1);
                j=j+m+1;
                i=m-1;
                flag=1;
            }
        if(flag==0){
                printf("Pattren has not found.\n");
            }
    }
}
 
void compute_g(char p[],int g[])
{
    int c,k;
    int m = strlen(p);
   
    for(c = 0;c <= 255;c++){
        g[c] = m-1;
    }
    for(k = 0;k <= m;k++){
        g[(int)p[k]] = m - k - 2;
    }
}
 
void compute_h(char p[])
{
    int m=strlen(p);
    int i,j;
    int f[m];
    int h[m];
   
    for(i=0;i<m;i++){
        h[i]=2*m-1-i;
    }
    i=m-1;
    j=m;
    f[m-1]=m;
    while(i>=0){
        if(j==m||p[i]==p[j]){
            i--;
            j--;
            f[i]=j;
        }else{
            h[j]=min(h[j],m-1-i);
            j=f[j];
        }
    }
    for(i=0;i<m;i++)
    {
        h[i]=min(h[i],m-1+j-i);
        if(i>j){
            j=f[j];
        }
    }
}
 
int max(int a, int b)
{
    if(a>b){
        return a;
    }else{
        return b;
    }
}
 
int min(int a, int b)
{
    if(a<b){
        return a;
    }else{
        return b;
    }
}

Name: かずま
[URL]
Date: 2017年11月28日(火) 05:29
No: 2
(OFFLINE)

 Re: ボイヤー・ムーア法について

関数 bm の中の配列 h は未初期化のまま参照されています。

関数 compute_h は、その配列 h を初期化するために
あるんでしょうが、やっていることは、関数 compute_h
のローカルな配列 h に値を設定しているだけで、これは
compute_h の終了とともに消えてしまいます。
compute_g が g を引数としているように compute_h が h
を引数として、bm の h を初期化しないといけないでしょう。

他にも変なところがありますが、とりあえず、このことを
指摘しておきます。

Name: hnkto
[URL]
ぴよぴよ(413 ポイント)
Date: 2017年11月28日(火) 14:54
No: 3
(OFFLINE)

 Re: ボイヤー・ムーア法について

ありがとうございます!まだまだ初心者なので間違えが多いことはご了承下さい^^;
他の関数がどのような働きをしているのかなども教えていただけると嬉しいです。

Name: かずま
[URL]
Date: 2017年11月28日(火) 20:44
No: 4
(OFFLINE)

 Re: ボイヤー・ムーア法について

よくわからない h[] を削除し、
g[] もちょっと変更してみました。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <string.h>
 
void compute_g(char [], int []);
void bm(char [], char []);
int max(int a, int b) { return a > b ? a : b; }
 
int main(void)
{
    char t[30];
    char p[10];
   
    strcpy(t, "ababdababccbdccabcadb");
    printf("テキスト:%s\n", t);
    printf("探したい文字列を入力してください:");
    scanf("%s", p);
    bm(t, p);
    return 0;
}
 
void bm(char t[], char p[])
{
    int m = strlen(p);
    int n = strlen(t);
    int i, j;
    int g[256];
   
    compute_g(p, g);
    for (i = m - 1; i < n; i += max(g[(unsigned char)t[i]], m - j))
        for (j = m - 1; t[i] == p[j]; i--, j--)
            if (j == 0) {
                printf("Pattern has found at %d.\n", i);
                return;
            }
    printf("Pattren has not found.\n");
}
 
void compute_g(char p[], int g[])
{
    int m = strlen(p);
    int i;
   
    for (i = 0; i < 256; i++)
        g[i] = m;
    for (i = 0; i < m - 1; i++)
        g[(unsigned char)p[i]] = m - i - 1;
}

大学のアルゴリズムの授業で学んでいるのなら
h[] の意味を日本語で説明してもらえませんか?

Name: かずま
[URL]
Date: 2017年12月01日(金) 19:48
No: 5
(OFFLINE)

 Re: ボイヤー・ムーア法について

ウィキペディアの ボイヤー-ムーア文字列検索アルゴリズム
を参考に h[] を作ってみました。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
#include <stdlib.h>
 
void compute_g(char p[], int g[])
{
    int m = strlen(p);
    int i;
 
    for (i = 0; i < 256; i++) g[i] = m;
    for (i = 0; i < m - 1; i++) g[(unsigned char)p[i]] = m - 1 - i;
}
 
void compute_h(char p[], int h[])
{
    int m = strlen(p);
    int x = m - 1;
    int i, k;
 
    for (k = m - 1; k >= 0; k--) {
        int o = k + 1, s = m - o;
        for (i = 0; i < s; i++)
            if (p[i] != p[o + i]) break;
        if (i == s) x = k + 1;
        h[k] = x + m - 1 - k;
    }
    for (k = 0; k < m - 1; k++) {
        for (i = 0; p[k - i] == p[m - 1 - i] && i < k; i++) ;
        if (p[k - i] != p[m - 1 - i]) h[m - 1 - i] = m - 1 - k + i;
    }
}
 
void bm(char *t, char *p)
{
    int n = strlen(t);
    int m = strlen(p);
    int i, j;
    int g[256];
    int h[1024];
 
    compute_g(p, g);
    compute_h(p, h);
    for (i = m - 1; i < n; i += max(g[(unsigned char)t[i]], h[j]))
        for (j = m - 1; t[i] == p[j]; --i, --j)
            if (j == 0) {
                printf("Pattern has found at %d.\n", i);
                return;
            }
    printf("Pattren has not found.\n");
}
 
int main(void)
{
    char t[] = "ababdababccbdccabcadb";
    char p[1024];
   
    printf("テキスト:%s\n", t);
    while (1) {
        printf("探したい文字列を入力してください:");
        if (scanf("%s", p) != 1 || p[0] == '.') break;
        bm(t, p);
    }
    return 0;
}


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[11人]