最近字符串

在理论计算机科学中，最近字符串试图找到一组输入字符串的几何中心，是一个NP 难的计算问题 ，

要理解字符串的“中心”，就必须先定义两个字符串之间的距离。通常，该问题下的距离是指汉明距离。

正式定义
更正式地说，给定n 个长度为 m 的字符串 s_1, s_2, ..., s_n，最近字符串问题旨在寻找一个长度为m 的新字符串s，使得\max_{i=1, 2, , ..., n} d(s, s_i) = k 尽可能小，其中d是汉明距离。 最近字符串问题的判定版本（NP 完全问题）则将k作为另一个输入，并询问是否存在一个字符串与所有输入字符串的汉明距离在k以内。 。但由于隐藏常数较大，该方案实际上无法使用。

固定参数可解性
最近字符串问题可以在O(kL+kd\cdot d^d)时间内解决。

其中k为输入字符串的数量， L为所有字符串的长度， d为解字符串到任意输入字符串的期望最大距离。

当参数d固定时，该问题便退化为多项式时间内可解。

与其他问题的联系
最近字符串串问题是更一般的问题的一个特例，后者难度更高：

最近字符串问题虽然是固定参数可解的，但是固定参数的最近子串问题是[[参数复杂性|W[1] 难]]问题。

参考