字符串匹配:匹配带空格或不带空格的单词

Question

在以下两个例子中，我想找到一种将"bmw“映射到”bmw“和”阿里巴巴“到"alibaba”的方法。

1. "b m w商店“和"bmw”

我需要确定我是否可以把"bmw“写成”bmw“。

我想到了这种方法：

从原始字符串中删除空格。这就产生了“bmwshop”。现在可以在"bmwshop“和"bmw”中找到最大的通用子字符串。

第二个例子：

1. 阿里巴巴40个小偷和阿里巴巴40个小偷

在这种情况下，上述方法不起作用。

有什么标准的算法可以使用吗？

Answer 1

听起来您在问这个问题：“如何通过删除(一些)空格来确定字符串A是否等于字符串B？”

您可以做的是对两个字符串进行迭代，当它们具有相同的字符时，在这两个字符串中进行迭代，否则，当第一个字符串有一个空格时，沿着第一个字符串前进，否则返回false。如下所示：

static bool IsEqualToAfterRemovingSpacesFromOne(this string a, string b) {
    return a.IsEqualToAfterRemovingSpacesFromFirst(b)
        || b.IsEqualToAfterRemovingSpacesFromFirst(a);
}
static bool IsEqualToAfterRemovingSpacesFromFirst(this string a, string b) {
    var i = 0;
    var j = 0;
    while (i < a.Length && j < b.Length) {
        if (a[i] == b[j]) {
            i += 1
            j += 1
        } else if (a[i] == ' ') {
            i += 1;
        } else {
            return false;
        }
    }
    return i == a.Length && j == b.Length;
}

以上只是一个修改过的字符串比较。如果要将其扩展到“最大公共子字符串”，则采用最大的公共子字符串算法，并执行类似的操作:每当您由于第一个字符串中的空格而失败时，只需跳过它。

Answer 2

你看过后缀数组 - 数组还是Jon Bentley - 节目珍珠的

注意事项：您必须编写代码来处理空格。