9

对于数组长度为 5 的简单问题（实际上数组长度可能为 20..）

我有一组预定义的模式，例如AAAAB、AAABA、BAABC、BCAAA、 ...。每个模式与输入数组的长度相同。我需要一个函数，它将任何整数数组作为输入，并返回它匹配的所有模式。（一个数组可能匹配一些模式）尽可能快。

“ A ”表示模式中A位置上的所有数字都相等。例如AAAAA仅表示所有数字都相等，{1, 1, 1, 1, 1}匹配AAAAA。

“ B ”表示B 位置的数字不等于A 位置的数字。（即非A数字的通配符） B 表示的数字不必相等。例如ABBAA表示第 1、4、5 个数字等于 x，而第 2、3 个数字不等于 x。 {2, 3, 4, 2, 2}匹配ABBAA。

“ C ”表示该位置可以是任何数字（即数字的通配符）。{1, 2, 3, 5, 1}匹配ACBBA， {1, 1, 3, 5, 1}也匹配ACBBA

我正在寻找一种有效的（就比较数而言）算法。它不必是最优的，但不应该是最优的。我觉得它有点像决策树...

一个非常简单但效率低的方法如下所示：

  • 尝试将每个模式与输入进行匹配。对{a, b, c, d, e}说AABCA。它检查是否.(a=b=e && a!=c)

  • 如果模式的数量是n，模式/数组的长度是m，那么复杂度大约是O(n*m)

更新：

请随时为问题提出更好的措辞，因为我不知道如何使问题简单易懂而不会造成混淆。

理想的算法需要某种准备，例如将模式集转换为决策树。因此对于某些特殊模式集，预处理后的复杂性可以达到 O(log n * log m) 之类的东西。（只是猜测）

一些可能有用的数字：预定义模式集的大小约为 30。要匹配的输入数组的数量约为 1000 万。

比如说，如果AAAAA和AAAAC都在预定义的模式集中。那么如果AAAAA匹配，则 AAAAC 也匹配。我正在寻找一种可以识别的算法。

更新 2

@Gareth Rees 的答案给出了一个 O(n) 解决方案，但假设没有很多“ C ”。（否则存储量很大，很多不必要的比较）

我也欢迎任何关于如何处理有许多“ C ”的情况的想法，例如，对于长度为 20 的输入数组，每个预定义模式至少有 10 个“ C ”。

4

2 回答 2

6

这是一个将 O(2 n ) 准备和存储换成 O( n )-ish 运行时的想法。如果您的数组不超过您机器的字长（您暗示 20 是典型的大小），或者如果模式中没有太多C出现，那么这个想法可能对您有用。（如果这两个条件都不满足，请避免！）

  1. （准备步骤，完成一次。）创建字典d将数字映射到模式集。对于每个模式p以及该模式中出现的C的每个子集S，令n是具有对应于模式中每个A的设置位的数字，并且对于S中的每个C出现。将p添加到模式集d [ n ] 中。

  2. （每次需要将新数组与模式匹配时，都会执行剩余步骤。）创建一个字典，将数字映射到数字。

  3. 让j遍历数组的索引，并且对于每个j：

    1. 设i为数组中的第j个整数。

    2. 如果i不在字典e中，则设置e [ i ] = 0。

    3. 设置e [ i ] = e [ i ] + 2 ℓ - j - 1其中 ℓ 是数组的长度。

  4. 现在e的键是数组中不同的数字i，值e [ i ] 有一个设置位，对应于数组中i的每次出现。对于字典d中找到的每个值e [ i ]，集合d [ e [ i ]] 中的所有模式都与数组匹配。

（注意：在实践中，您会以相反的方式构建位集，并在步骤 3.3 中使用 2 j而不是 2 ℓ − j − 1，但为了清楚起见，我已经以这种方式描述了算法。）

Here's an example. Suppose we have the patterns AABBA and ACBBA. In the preprocessing step AABBA turns into the number 25 (11001 in binary), and ACBBA turns into the numbers 25 (11001 in binary) and 17 (10001 in binary), for the two possible subsets of the occurrences of C in the pattern. So the dictionary d looks like this:

  • 17 → {ACBBA}
  • 25 → {AABBA, ACBBA}

After processing the array {1, 2, 3, 5, 1} we have e = {1 → 17, 2 → 8, 3 → 4, 5 → 2}. The value e[1] = 17 is found in d, so this input matches the pattern ACBBA.

After processing the array {1, 1, 2, 3, 1} we have e = {1 → 25, 2 → 4, 3 → 2}. The value e[1] = 25 is found in d, so this input matches the patterns AABBA and ACBBA.

于 2012-12-15T21:08:43.770 回答
0

获取模式中第一个的索引A，获取该位置的值，然后遍历这些位置。

要检查数组是否array与字符串中的模式匹配pattern，结果在布尔值中match：

int index = pattern.IndexOf('A');
int value = array[index];
bool match = true;
for (int i = 0; i < array.Length; i++) {
  if (pattern[i] != 'C' && i != index) {
    if ((pattern[i] == 'A') != (array[i] == value)) {
      match = false;
      break;
    }
  }
}
于 2012-12-15T18:43:54.480 回答