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

[hnkto]

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

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

コード:

#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;
    }
}

[かずま]

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

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

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

[hnkto]

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

[かずま]

よくわからない h[] を削除し、
g[] もちょっと変更してみました。

コード:

#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[] の意味を日本語で説明してもらえませんか？

[かずま]

ウィキペディアの ボイヤー-ムーア文字列検索アルゴリズム
を参考に h[] を作ってみました。

コード:

#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;
}