BM法でテキストの中からパターンの個数を数えるには？

[CPU]

初投稿です。
BM法でパターンが何文字目に出るのかという検索はできるのですが、
入力したテキストの中にパターンが何個含まれているのかカウントするプログラムがうまくいきません。

テキスト：AAAAA
パターン：A
結果：５

テキスト：AAAAA
パターン：AA
結果：４

テキスト：ABABCDEFGHABC
パターン：ABC
結果：２

テキスト：xxxxdcdexxxx
パターン：dcde
結果：１

これらすべてを満たすプログラムを教えてもらえないでしょうか？

[non]

学校の課題でしたら、どこまで習っているのかわかりませんので
>BM法でパターンが何文字目に出るのかという検索はできるのですが、
このプログラムを載せてください。
ポインタを使って良いのか、strstr関数は使って良いかなど記してください。
それに、関数は習っているのかなど。関数の仕様は。

[CPU]

一応作ってみたプログラムを載せます。
コメントアウトしてるものは試して失敗したものです。

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

int bm_count(char *pat, char *txt){
char *pt;
char *pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
int skip[UCHAR_MAX + 2];
int i, count = 0;

for(i = 0; i <= UCHAR_MAX; i++)
skip = pat_len;
for(pp = pat; *pp != '\0'; pp++)
skip[*pp] = strlen(pp) - 1;
skip[*(pp - 1)] = pat_len;
pt = txt + pat_len - 1;
while ( pt < txt + txt_len) {
pp = pat + pat_len - 1;
while (*pt == *pp) {
if(pp == pat) {
count++;
//pp = pat + pat_len -1;
pt += (skip[*pt]> pat_len - strlen(pp))? skip[*pt] : pat_len - strlen(pp);
//pp += (skip[*pp]> pat_len - strlen(pp))? skip[*pp] : pat_len - strlen(pp);
//pp += skip[*(pat + pat_len - 1)];
pp = pat + pat_len - 1;
//pp += skip[*pp];
}else{
pp--;
pt--;}
}
pt += (skip[*pt]> pat_len - strlen(pp))? skip[*pt] : pat_len - strlen(pp);
}
return(count);

}

int main(void)
{
int num;
char s1[80];
char s2[80];

printf("テキスト：");
scanf("%s", s1);

printf("パターン：");
scanf("%s", s2);

num = bm_count(s2, s1);

if (num == 0)
puts("テキスト中にパターンは存在しません。");
else
printf("%sの文字列の中に%sの文字列は%d個見つかりました。\n", s1, s2, num);
return (0);
}

[naohiro19]

「新・アルゴリズムとデータ構造」にサンプルプログラムが載っていますので参考になるかと思います。

[non]

添付されているプログラムは1個目の検索が正しく出ないような気がします。
私の勘違いかも知れませんが、ポインタの移動数にあやまりがあるような・・・・
個数を数えるプログラムでなく、BM法の正しく動くプログラムを添付してください。

[CPU]

下記のプログラムを応用させて作成するそうです。
#include <stdio.h>
#include <string.h>
#include <limits.h>

char *bm_count(char *pat, char *txt){
char *pt;
char *pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
int skip[UCHAR_MAX + 1];
int i;

for(i = 0; i <= UCHAR_MAX; i++)
skip = pat_len;
for(pp = pat; *pp != '\0'; pp++)
skip[*pp] = strlen(pp) - 1;
skip[*(pp - 1)] = pat_len;

pt = txt + pat_len - 1;
while ( pt < txt + txt_len) {
pp = pat + pat_len - 1;
while (*pt == *pp) {
if(pp == pat) return(pt);
pp--;
pt--;
}
pt += (skip[*pt]> pat_len - strlen(pp))? skip[*pt] : pat_len-strlen(pp);
}
return(NULL);
}

int main(void)
{
char *s;
char s1[80];
char s2[80];

printf("テキスト：");
scanf("%s", s1);

printf("パターン：");
scanf("%s", s2);

s = bm_count(s2, s1);

if (s == NULL)
puts("テキスト中にパターンは存在しません。");
else
printf("%d文字目に見つかりました。\n", s - s1 + 1);
return (0);
}

[non]

>pt += (skip[*pt]> pat_len - strlen(pp))? skip[*pt] : pat_len-strlen(pp);
やっぱりここがおかしそうですね。

たとえば、テキスト
abcabc
パターン
bca
で試したら、存在しませんになります。

[CPU]

先生から指示があった内容ではこれでいけると言われました。
講義で使っている教科書もその部分で書いてあるんですよ。
間違えてるとしか思えないんですけどどうですかね。

[CPU]

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

int bm_count(char *pat, char *txt){
char *pt;
char *pp;
int txt_len = strlen(txt);
int pat_len = strlen(pat);
int skip[UCHAR_MAX + 2];
int i, count = 0;

for(i = 0; i <= UCHAR_MAX; i++)
skip = pat_len;
for(pp = pat; *pp != '\0'; pp++)
skip[*pp] = strlen(pp) - 1;
skip[*(pp - 1)] = pat_len;
pt = txt + pat_len - 1;
while ( pt < txt + txt_len) {
pp = pat + pat_len - 1;
while (*pt == *pp) {
if(pp == pat) {
count++;
break;
}else{
pp--;
pt--;}
}
pt += (pat_len - strlen(pp) != 0) ? skip[*pt] : pat_len;
}
return(count);

}

int main(void)
{
int num;
char s1[80];
char s2[80];

printf("テキスト：");
scanf("%s", s1);

printf("パターン：");
scanf("%s", s2);

num = bm_count(s2, s1);

if (num == 0)
puts("テキスト中にパターンは存在しません。");
else
printf("%sの文字列の中に%sの文字列は%d個見つかりました。\n", s1, s2, num);
return (0);
}

上記のプログラムがただひとつ以外すべて通りました。
ただ通らなかったのが
テキスト：xxxxdcdexxxx
パターン：abcde
が無限ループに入りました。

[non]

どっちのプログラムが先生(または教科書）なのかよくわかりませんが、うまく動かないのは事実でしょ。
で、私が、ここがおかしいよと言っているのに、チェックしないのですね。
面倒なので、1個目を検索するプログラムを載せます。その上で、個数を数えられるように考えてみてください。

コード:

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

char *bm_count(char *pat, char *txt){
	char *pt;
	char *pp;
	int txt_len = strlen(txt);
	int pat_len = strlen(pat);
	int skip[UCHAR_MAX + 1];
	int i;

	for(i = 0; i <= UCHAR_MAX; i++)
		skip[i] = pat_len;
	for(pp = pat; *pp != '\0'; pp++)
		skip[*pp] = strlen(pp) - 1;
	skip[*(pp - 1)] = pat_len;

	pt = txt + pat_len - 1;
	while ( pt < txt + txt_len) {
		pp = pat + pat_len - 1;
		while (*pt == *pp) {
			if(pp == pat) return(pt);
			pp--;
			pt--;
		}
		pt += (skip[*pt]> strlen(pp))? skip[*pt] : strlen(pp);
	}
	return(NULL);
}

int main(void)
{
	char *s;
	char s1[80];
	char s2[80];

	printf("テキスト：");
	scanf("%s", s1);

	printf("パターン：");
	scanf("%s", s2);

	s = bm_count(s2, s1);

	if (s == NULL)
		puts("テキスト中にパターンは存在しません。");
	else
		printf("%d文字目に見つかりました。\n", s - s1 + 1);
	return (0);
}

[CPU]

いろいろとお手数をおかけしました。
そのプログラムを少し変えたらできました。

ありがとうございました