例如，我得到以下由 0 和 1 组成的字符串:001011。 这是我的模式，或字符串 A。 然后，我得到一个更长的 0 和 1 字符串 B(例如:010100010010010)，我的任务是在 B 中找到字符串 A 最合适的匹配项，我说 ,,the most appropriate"因为它不需要一定是字符串A，最大误差20%。
例如:对于字符串 A:01001，一个好的匹配应该是 11001。字符串 B 的 80% 与字符串 A 匹配，除了第一位。对于同一个 A 字符串，11101 只会匹配它的 60%(11101 中第一和第三位的位与 A 中的第一和第三位不匹配)，这不是理想的解决方案。
如果 N 是字符串 A 的位数，这意味着我立即对 B 的 N 长度序列执行检查(B 中的评估位必须在连续的位置上，因此这排除了 B 中的子字符串).例如: 让它成为 A-01011 和 B-010100100111。首先，我们评估序列 01010(B 的前 5 位从第一个位置开始)，然后是 10100(前 5 位从 B 的第二位开始)。在此示例中，在 01010 中只有 4 位与 A 匹配，这意味着 01010 是 80% 匹配。对于10100，没有比特与A匹配，因此是0%匹配。
我可能遇到这样一种情况，A 是:01001，B 是:01101(B 的前 2 位与 A 的前 2 位匹配，B 的后 2 位与 A 的后 2 位匹配)。因此，这是一个 80% 的匹配。
如果 A 比 B 长，则 A 在 B 中没有匹配。
我想知道一个算法，解决这个问题的策略。我希望我尽可能清楚地说明了这个问题，如果没有，我将修改或为您提供进一步的解释。我认为这个问题实际上可能在现实世界中有一些关于模式匹配的应用。 我需要一个解决方案，我期待着尽可能改进解释。
最佳答案
所以你实际上只是比较二进制数。因此，将字符串转换为数字并将它们进行二进制比较。所以使用 XOR 位运算 ( https://en.wikipedia.org/wiki/Bitwise_operation ), (in C ^)
11001 ^ 11101 = 00100
0 ^ 0 = 0
1 ^ 0 = 1
0 ^ 1 = 1
1 ^ 1 = 0
(这取自 How to compare two bit values in C?。也许这是重复的？)。
在 python 中添加代码，可能不是最优的但可能有用
def bitcount(n):
count=0
while(n):
count+= (n & 1)
n >>=1
return count
a="01011"
b="010100010010010"
number= int(a, 2)
new = []
result=[]
for i in range(0, len(b)-len(a)):
new.append(int(b[i:i+len(a)],2))
compare = number ^ new[i]
if(bitcount(compare) < int(0.2*len(a))+1):
print(b[i:i+len(a)])
我认为这与 (len(b)-len(a))*len(a) 成比例。 O(a b) 如果我错了请纠正我？..
关于string - 我有一个特定的 1's and 0' 字符串，我想在另一个字符串中找到最合适的匹配项，最大误差为 20%，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42089536/