如何使用C-示例中的动态编程在两个数组之间的一行中找到相同的元素

Question

严重的问题，因为我要完成我的毕业论文，我无法找到最后的问题，以完成我的项目.

我创造了两个图像来解释我的问题..。

，如果有人真的能帮忙的话，我会很感激的。谢谢.

​

​

​

​

Answer 1

在这种情况下，您可以利用这样的事实:数组只能包含两个可能的值，并且子字符串的长度很短。

您正在寻找长度为4的子串，它们仅由0和1s组成。有16个这样的子字：

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

这些是从0到15的二进制数。创建一个长度为16的数组，该数组存储第一个数组中对应模式的第一个出现位置。然后创建一个滑动窗口，该窗口访问每个4元素子字符串并确定模式id：

        0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0      pos[3] == 0
        <--- 3 -->

        0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0      pos[6] == 1
           <--- 6 -->

        0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0      pos[12] == 2
              <-- 12 -->

        0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0      pos[9] == 3
                 <--- 9 -->

现在，对第二个数组执行同样的操作。如果设置了第一个数组中相同模式的位置，则有一个匹配。

下面的代码就是这样做的，并显示了第一个匹配。(首先是关于第二个数组中的模式位置。)不过，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发生在第二个数组的位置0和4处。你必须把这两个位置都储存起来。那么，某一模式的所有位置组合都是匹配的。

下面的代码打印所有可能的匹配。它实现了一种链表，其中head在每个模式的第一次出现，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;
}