查询字符串是否相同的查询

4 回答

• 2

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

  等价关系似乎基本上检查匹配字符串的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;
  }
  

  回复于 2024-04-27T02:48:01+08:00
• 0

  让A，B，你的2个长度为N的字符串 .

  令A2，B2,2矩阵N×N，其中A2（i，j）= A [i] == A [j] .

  所以：

  for 1 <= i,j <= N
  {
    A2(i,j) = A[i] == A[j]
    B2(i,j) = B[i] == B[j]
  }
  

  然后比较2矩阵是相当长的 . 但矩阵仅包含 {1,0} . 因此，不要考虑 A2 矩阵，而是可以使用布尔值的向量（在c或java / c＃中的列表中） .

  让Va，Yb，两个布尔矢量（对于A和B分别）：

  for 1 <= i,j <= N
  {
    Va(i * N + j) = A[i] == A[j]
    Vb(i * N + j) = B[i] == B[j]
  }
  

  然后，您的 property 相当于Va == Vb .

  在速度方面，您可以改进实施，从而减少内存使用量 . 64位整数车存储64个值 .

  所以，再次：

  所以让V64_a，Y64_b，两个64位无符号向量（对于A和B分别）的长度为（N * N / 64）的向量1：用0开始它们 .

  for(i=1 ; i< N ; i++)
  {
    // special case, comparing ith char with ith char : always true
    Va[i*i/64] = Va[i*i/64] | (1 << i%64)
    Vb[i*i/64] = Vb[i*i/64] | (1 << i%64)
  
    for( j=i+1 ; j < N ; ++j)
    {
      Va[i*i/64] = Va[i*i/64] | ((A[i] == A[j] ? 1 : 0 ) << i%64)
      Vb[i*i/64] = Vb[i*i/64] | ((B[i] == B[j] ? 1 : 0 ) << i%64)
    }
  }
  

  然后，A == B <=> Va == Vb .

  回复于 2024-04-27T02:48:01+08:00
• 1

  好的，这里是完全工作的Java示例，复杂度为O（k），每个查询都没有任何预处理 .

  import java.util.ArrayList;
  import java.util.HashMap;
  import java.util.List;
  import java.util.Map;
  
  public class JavaApplication14 {
      public static void main(String[] args) {
          String a = "abbcd";
          String b = "cccad";
  
          equivalency(a, b, 3, 3, 3);
          equivalency(a, b, 1, 1, 2);        
      }
  
      public static void equivalency(String a, String b, int i, int j, int k){
          List<Character> orderA = new ArrayList<>();
          List<Character> orderB = new ArrayList<>();
  
          Map<Character, List<Integer>> mapA = createMap(a, i, k, orderA);
          Map<Character, List<Integer>> mapB = createMap(b, i, k, orderB);
  
          if (orderA.size() != orderB.size()) {
              System.out.println("NO");
              return;
          }
  
          for (int l = 0; l < orderA.size(); l++) {
              List<Integer> valuesA = mapA.get(orderA.get(l));
              List<Integer> valuesB = mapB.get(orderB.get(l));
  
              if (valuesA.size() != valuesB.size()) {
                  System.out.println("NO");
                  return;
              }
  
              for (int m = 0; m < valuesA.size(); m++) {
                  if (valuesA.get(m).equals(valuesB.get(m)) == false) {
                      System.out.println("NO");
                      return;
                  }
              }
          }
  
          System.out.println("YES");        
      }
  
      public static Map<Character, List<Integer>> createMap(String input, int pos, int count, List<Character> characterOrder) {
          Map<Character, List<Integer>> map = new HashMap<>();
          input = input.substring(pos-1, pos+count-1);
  
          for (int i = 0; i < input.length(); i++) {
              char ch = input.charAt(i);
              if (map.containsKey(ch) == false) {
                  characterOrder.add(ch);
                  map.put(ch, new ArrayList<>());
              }
  
              map.get(ch).add(pos);
          }
  
          return map;
      }
  }
  

  此示例的输出是：

  YES
  NO
  

  （如果你发现输入的输出应该比这个程序实际有的不同，请告诉我，我会修复它）

  ---

  它实际上做了什么？当您查看比较的两个字符串中的第一个字符时，相同字符（对于每个字符串）的位置必须出现在与另一个字符串相同的位置 . 如果没有，则不相等 . 并且它与任何其他角色相同 - 第二个角色必须在两个字符串等中具有相同的外观位置列表 .

  此代码为每个字符创建外观列表并将其保留在此结构中： Map<Character, List<Integer>> ，您还需要知道首先找到哪个字符，哪个字符用于比较这些位置，所以为此我使用 List<Character> .

  在方法结束时，我首先在字符串A中发现字符，在 Map 中找到它返回其外观的结构 . 我对String B做了同样的事情 . 然后我比较了字符串A和字符串B的所有值 . 如果它适合，我继续下一个字符，如果没有，它就不一样了 .

  回复于 2024-04-27T02:48:01+08:00
• 0

  对于从1到 k 的每个字符位置 pos ，来自 A 和 B 的相应字符 a 和 b 都需要首次出现或者像以前一样进行配对 . 使用java Collections，检查这个的一种方法是在 Map m 中 put(a, b) ：如果结果既不等于 null 也不等于 b ，答案应该是NO . 如果所有相等的 a 被映射到相等 b s，则仍然需要检查是否将不同的 a s映射到不同的 b ，如果 values() 是唯一的，那么它应该为真

  Collection<Character> values = m.values();
  return new HashSet(values).size() == values.size() ? YES : NO;
  

  （或者，重复检查以反转 A 和 B 的角色或并行执行这些检查或......）
  如果查询的数量证明预处理是合理的，那么保持数组 bdA 和 bdB 为"backward distances"：前一个位置的最后一个字符返回前后多远？ （如果没有，请使用 N+1 . ）对于查询， pos 从 2 到 k ，如果 bdA[i + pos] != bdB[j + pos] 且至少有一个低于 pos ，答案应该是没有 . （如果两者都等于或高于 k ，则两者都是范围内的第一次出现 . ）

  回复于 2024-04-27T02:48:01+08:00