Cでダイナミックプログラミングを使用して2つの配列間で同じ要素を見つける方法 - 例

Question

私はディプロマのための私の論文を終えているので、私はこの問題を最後に把握できません。 。

誰もが本当に私はそれを感謝します助けることができるなら、私は、私は私の問題を説明してる2枚の画像...

を作成します。あなたのケースのおかげで...

Answer 1

、あなたの配列が2つだけの可能な値を含み、サブストリングの長さが短いということができるという事実を利用することができます。

長さ4の部分文字列が0と1のみで構成されているかどうかを調べています。 16のこのようなサブストリングがあります

 0000 0001 0010 0011 
     0100 0101 0110 0111 
     1000 1001 1010 1011 
     1100 1101 1110 1111 

これらは0から15までの最初の配列に対応するパターンの最初の発生の位置を格納する長さ16の配列を作成したバイナリ数です。次に、4要素の部分文字列をすべて調べ、パターンIDを決定するスライディングウィンドウを作成します。

2番目の配列で同じことを行います。最初の配列の同じパターンの位置が設定されている場合は、一致するパターンがあります。

以下のコードはこれを行い、最初の一致を示しています。 （最初の配列のパターン位置に関して）pos配列は部分文字列の終わりを格納します。

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

enum {M = 12, N = 12, K = 4}; 

int find(const int *a, int m, const int *b, int n, int k, int *pa, int *pb) 
{ 
    int k2 = 1 << k; 
    int kmask = k2 - 1; 

    int apos[k2]; 
    int bpos[k2]; 

    unsigned int apat = 0u; 
    unsigned int bpat = 0u; 

    int i; 

    *pa = *pb = -1; 

    if (m < k || n < k) return 0; 

    for (i = 0; i < k2; i++) apos[i] = -1; 
    for (i = 0; i < k2; i++) bpos[i] = -1; 

    for (i = 0; i < k; i++) { 
     apat = (apat << 1) | a[i]; 
     bpat = (bpat << 1) | b[i]; 
    } 

    for (i = k; i < m; i++) { 
     if (apos[apat] == -1) apos[apat] = i; 
     apat = ((apat << 1) & kmask) | a[i]; 
    } 

    for (i = k; i < n; i++) { 
     if (apos[bpat] != -1) { 
      *pa = apos[bpat] - k; 
      *pb = i - k; 

      return 1; 
     } 

     bpat = ((bpat << 1) & kmask) | b[i]; 
    } 

    return 0; 
} 

int main(void) 
{ 
    int a[M] = {0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0}; 
    int b[N] = {1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}; 

    int ia, ib; 

    if (find(a, M, b, N, K, &ia, &ib)) { 
     printf("[a: %d, b: %d]\n", ia, ib); 
    } else { 
     puts("No match."); 
    } 

    return 0; 
} 

この基本コードは、あなたが探しているものに応じて変更することができます。

• あなただけシングルマッチをしたい場合は、あなたがの長さを二つの配列を通過することができより短いものを同時に実行するようにしてください。早いマッチがある場合は、配列全体を走査する必要はありません。あなたはどのパターンが共通しているかを知りたい場合は

• 、配列を横断して、それぞれの位置のaposとbposを追跡します。位置が両方の位置アレイに存在する場合、対応するパターンは両方のアレイに共通です。

• がすべてと一致する必要がある場合は、パターンに対応するすべての位置を保存する必要があります。たとえば、パターン1000または8は、2番目の配列の位置0および4にあります。両方のポジションを保存する必要があります。次に、特定のパターンのすべての組み合わせが一致します。

以下のコードはすべての一致を示しています。それは、headが各パターンの最初の出現をkeptし、特定の位置で同じパターンの次の出現をnextのような種類のリンクされたリストを実装します。

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

enum {M = 12, N = 12, K = 4}; 

void list(const int *a, int m, int k, int *head, int *next) 
{ 
    int k2 = 1 << k; 
    int i; 

    unsigned int pat = 0u; 

    for (i = 0; i < k2; i++) head[i] = -1; 

    for (i = m - k + 1; i < m; i++) pat = (pat << 1) | a[i]; 
    pat <<= 1; 

    i = m - k + 1; 
    while (i--) { 
     pat = (pat | (a[i] << k)) >> 1; 

     next[i] = head[pat]; 
     head[pat] = i;   
    } 
} 

int main(void) 
{ 
    int a[M] = {0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0}; 
    int b[N] = {1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0}; 

    int ahead[1 << K]; 
    int bhead[1 << K];  

    int anext[M - K + 1];  
    int bnext[N - K + 1]; 
    int i; 

    list(a, M, K, ahead, anext); 
    list(b, N, K, bhead, bnext); 

    for (i = 0; i < (1 << K); i++) { 
     int pa = ahead[i]; 

     while (pa != -1) { 
      int pb = bhead[i]; 

      while (pb != -1) { 
       printf("a: %d, b: %d\n", pa, pb); 
       pb = bnext[pb]; 
      } 

      pa = anext[pa]; 
     } 
    } 

    return 0; 
}