java - 检查字符串是否等价的查询

Question

给定 2 个长度相同的字符串 A 和 B，如果以下条件对所有 1 <= i, j <= N 都为真，则认为它们是等价的:

(Ai != Aj) <=> (Bi != Bj)
(Ai = Aj) <=> (Bi = Bj)

哪里S[i]表示字符串 S 的第 i 个(从 1 开始索引)字符。

注意:如果字符串 A 和 B 等价，则字符串 B 和 C 等价，则字符串 A 和 C 也等价。

给定 2 个长度为 N 的字符串 A 和 B。我们需要回答 Q 个查询。每个查询由 3 个整数 i、j、k 组成，对于给定的查询，我们需要检查字符串是否为 A[ i, i + k - 1]。和 B[ j, j + k - 1]是否等价。

例子:设A = "abbcd"和 B = "cccad"我们有 2 个查询:

Query 1 : i=1 , j=1 and k=2 then answer is NO

Query 2 : i=3 , j=3 and k=3 then answer is YES

以最有效的方式回答此查询的最佳方式是什么？我认为可以通过存储所有 26 个英文字母的位置然后进行二进制搜索类型的方法来进行一些预处理。但在某些情况下它会失败。那么如何解决给定字符串和 Q 查询的这个问题。

Answer 1

想法:创建一个规范化函数，让我们通过对“规范化”字符串进行常规字符串匹配来检查一对字符串的等价关系。

等价关系似乎基本上检查了一个 simple substitution cipher存在匹配的字符串。因此，对于规范化步骤，我们使用一个根据字母的首次出现来替换字母的步骤(Java 代码):

String normalize(String s) {
  char available = 'A';
  Map<Character, Character> seen = new HashMap<Character, Character>();
  StringBuilder result = new StringBuilder();
  for (int i = 0; i < s.length; s++) {
    char c = s.charAt(i);
    Character replacement = seen.get(c);
    if (replacement == null) {
      replacement = available++;
      seen.put(c, replacement);
    }
    result.append(replacement);
  }
  return result.toString();
}

在查询中使用规范化:

boolean query(String a, String b, int i, int j, int k) {
  return normalize(a.substring(i - 1, i + k)).equals(
         normalize(b.substring(j - 1, j + k)));
}

现在我们可以将它集成到一个专门的函数中，避免所有的复制:

boolean query(String a, String b, int i, int j, int k) {
  Map<Character, Character> seenA = new HashMap<Character, Character>();
  Map<Character, Character> seenB = new HashMap<Character, Character>();
  char available = 'A';
  for (int p = 0; p < k; p++) {
    char ca = a.charAt(i + p - 1);
    char cb = b.charAt(j + p - 1);
    Character replacementA = seenA.get(ca);
    Character replacementB = seenB.get(cb);
    if (replacementA == null ? replacementB != null :
        !replacementA.equals(replacementB)) {
      return false;
    }
    if (replacementA == null) {
      seenA.put(ca, available);
      seenB.put(cb, available);
      available++;
    }
  }
  return true;
}