c言語 任意の連続した数が、ある配列にあるかどうかを判定する方法を教えてください。

Question

c言語でプログラムを書いています。
2つの配列AとBがあります。配列AよりBのほうが要素数は多く、それぞれの配列の各要素には一桁の値が入っています。
配列Aに格納されている数が、連続して配列Bに存在するかどうかを調べる方法を教えてください。
よろしくお願いします。

例）
A[]={1, 2, 3} B[]={2, 5, 1, 2, 1, 2, 3, 8, 4}
配列Bの5つ目から7つ目にかけて、配列Aと同じ数が格納されているので、判定○

A[]={1, 2, 3} B[]={8, 4, 6, 2, 8, 9, 4, 7}
配列Aの数がどこにも連続した状態で配列Bに格納されていないので、判定×

配列A,Bの要素数は任意とします。

Answer 1

文字列検索アルゴリズムとしてBM法があります。
有名なアルゴリズムですので探せば解説してるサイトがたくさんあります。

また亜種にBMH法やquick searchがあります。

Answer 2

#include <stdio.h>

#include <string.h>

#define BUFSIZE 256

int main(void)
{
	int a[3] = {1, 2, 3};
	int b[9] = {2, 5, 1, 2, 1, 2, 3, 8, 4};
	int i,j;
	int pos;
	int flag = 0;
	int m,n;
	m = sizeof(b) / sizeof(int);
	n = sizeof(a) / sizeof(int);
	for(i = 0; i <= m - n; i++){
		if(b[i] == a[0]){
			pos = i;
			for(j = 0; j < n; j++){
				if(b[pos + j] == a[j]){
					flag = 1;
				}
				else{
					flag = 0;
					break;
				}
			}
		}
	}
	if(flag == 1){
		printf("%d番目から%d番目にかけてあるのでYES",pos,pos + n);
	}
	else{
		printf("NO");
	}

	return 0;
}

Answer 3

まず、要素が全一致するか判定する関数を書きます。

bool is_same_array(int const *A, int const *B, size_t len) {
    ...
}

あとは範囲外アクセスに注意しつつループをぶん回し、
is_same_array(A, &B[i], 3)が真になるiが存在するか判定すれば良いです。

Answer 4

どのくらいの要素数あるのかわからないので、上記の例を判別する力ずくのやり方を記載しておきます。

int i=0;
bool a;

while(1)
{
   if(A[0]==B[i] && A[1]==B[i+1] && A[2]==B[i+2])
   {
    a=true;
    break;
   }
   if(B[i+2]==NULL)
   {
    a=false;
    break;
   }
}

おそらくこれでいけると思いますが、今手元に動かせる環境がないためテストしてません。

参考までに…

Answer 5

考え方はstrstr()と同じなので

という回答で、思わず、最後に 0 を追加すれば、そのまま、strstr()で良いんじゃないかと思ったのですが、こちらは、char の配列が対象でした。
内容には、そのままで、検索アルゴリズムそのままですね。

さて、実際の方法としては、(効率の問題はありますが)
A[0] の数字 (今回は、1)を B[]を先頭から、探します。
<-- B[]の最後まででなく、A[]の長さ分前まで。
もし、見つからなければ、 --> 無し (×)
見つかれば、その次の数字から、A[]の数字と同じが判定する。
一致すれば、 ◯
不一致ならば、次の B[]から同じ事を繰り返す。

と言ったところでしょうか。
実際のコードは考えてください。 (スマートなコードにならなかったのでとりあえず、パス)

Answer 6

考え方はstrstr()と同じなので、strstr()の実装例を探すとか。