php - 获取 PHP 或 MySQL 中重叠字符的数量？

Question

我想计算两个字符串比较中重叠字符的数量。假设您有这些比较:

       boel <-> baal
       boel <-> bol
beestenboel <-> boelsten
beestenboel <-> baastenb
      hallo <-> hello

结果一定是这样的:

BoeL         } b matches, o does not match,
BaaL         } e does not match, l matches.
               Result: overlap = 2

BOeL         } b matches, o matches, l matches
BO L         } e does not match (it's not present in the lower string).
               Result: overlap = 3

B EeSTENboel } b matches, e matches (because o is only present in the lower
BoElSTEN     } string), the second e is no longer present (since we have
               already consumed an e from the lower string, l does not match,
               s, t, e, n match successively.
               (Notice that b, e, o and l from the upper string will be ignored,
               since all characters from the lower string have already been
               consumed.)
               Result: overlap = 6

BeeSTENBoel  } b matches, the two e's do not match with the two a's, and again,
BaaSTENB     } s, t, e, n match.
               Result: overlap = 6

HaLLO        } h matches, a doesn't match
HeLLO        } l, l and o match.
               Result: overlap = 4

我怀疑我想得太复杂了...我怎样才能在 MySQL 或 PHP 中获得上述结果？

(我猜levenshtein算法和这个问题有关。)

Answer 1

这个描述让我想起了我在学习期间学到的所有 DNA 比对算法。我不太确定，你需要他们正在做的所有事情，但看看 Needleman-Wunsch和 Smith-Waterman .