检查两个字符串是否共享相同的重复字符模式。

Question

有没有一种高效的正则表达式可以断言两个字符串具有相同的重复字符模式？

("tree", "loaa") => true
("matter", "essare") => false
("paper", "mime") => false
("acquaintance", "mlswmodqmdlp") => true
("tree", "aoaa") => false

即使不使用正则表达式，我仍在寻找执行任务的最有效方式。

- Marco Toniut

---

这是一个有效的模式: ("tree", "aoaa") => true吗？ - lstern

不确定正则表达式是否是这种模式匹配的正确工具。为什么不将每个遇到的字母翻译成另一个已知的字母，然后对第二个字符串执行相同的操作，然后比较两者。所以，找到的第一个字符始终是a，第二个字符始终是b，依此类推。虽然不高效，但是可以实现。 - J. Steen

“同一模式”并不意味着“相同的重复字符”，而是字符串包含相同的字符位置/信息熵吗？因此，'abc' = 'def'，'aab' = 'ccd'，'fggh' != 'abcd'？ - newfurniturey

@Istern：不，那将是一个无效的模式。 - Marco Toniut

你如何定义“重复字符的模式”？ - Miserable Variable

Answer 1

最简单的方法可能是手动同时遍历两个字符串，并在此过程中建立一个字典（将相应字符进行匹配）：

if(input1.Length != input2.Length)
    return false;
var characterMap = new Dictionary<char, char>();
for(int i = 0; i < input1.Length; i++)
{
    char char1 = input1[i];
    char char2 = input2[i];
    if(!characterMap.ContainsKey(char1))
    {
        if (characterMap.ContainsValue(char2))
            return false;
        characterMap[char1] = char2;
    }
    else
    {
        if(char2 != characterMap[char1])
            return false;
    }
}
return true;

以同样的方式，您可以构建一个正则表达式。对于单个比较来说，这显然不是更有效的方法，但如果您将来想要检查一个重复模式是否与多个字符串匹配，这可能很有用。这次，我们将字符与它们的反向引用相关联。

var characterMap = new Dictionary<char, int>();
string regex = "^";
int nextBackreference = 1;
for(int i = 0; i < input.Length; i++)
{
    char character = input[i];
    if(!characterMap.ContainsKey(character))
    {
        regex += "(.)";
        characterMap[character] = nextBackreference;
        nextBackreference++;
    }
    else
    {
        regex += (@"\" + characterMap[character]);
    }
}
regex += "$";

对于 matter，它将生成这个正则表达式：^(.)(.)(.)\3(.)(.)$。对于 acquaintance，则生成这个：^(.)(.)(.)(.)\1(.)(.)(.)\1\6\2(.)$。当然，可以稍后优化这个正则表达式（例如，对于第二个正则表达式，可以使用 ^(.)(.)..\1.(.).\1\3\2$），但无论如何，这都会给你一个可重用的正则表达式，用于检查这一具体重复模式。

编辑：请注意，给定的正则表达式解决方案有一些问题。它允许将输入字符串中的多个字符映射到测试字符串中的单个字符（这将与您的最后一个示例相矛盾）。要获得正确的正则表达式解决方案，您必须进一步禁止已匹配的字符。因此，acquaintance 将生成这个可怕的正则表达式：

^(.)(?!\1)(.)(?!\1|\2)(.)(?!\1|\2|\3)(.)\1(?!\1|\2|\3|\4)(.)(?!\1|\2|\3|\4|\5)(.)(?!\1|\2|\3|\4|\5|\6)(.)\1\6\2(?!\1|\2|\3|\4|\5|\6|\7)(.)$

我想不到更简单的方法，因为你不能在（否定）字符类中使用反向引用。所以，如果你确实想要断言这一点，正则表达式可能最终不是最佳选择。

免责声明：我并不是真正的.NET大师，因此在构建字典或字符串时遍历数组可能不是最佳实践。但我希望您可以将其用作起点。

- Martin Ender

---

我正在写完全相同的答案。 - lstern

同样的情况，但我没能够快速地编写代码，只好选择一个描述性的版本，虽然有点不够详细。 - Sid Holland

谢谢，这正是我在寻找的答案。 - Marco Toniut

Answer 2

编辑：已接受的代码现在是正确的。这个将作为一种替代方案而存在（在几乎任何意义上都不如原来的好）。

    private static List<int> FindIndices(string str, char c, int ind)
    {
        var retval = new List<int>();
        int last = ind, temp;
        while (0 < (temp = str.IndexOf(c, last)))
        {
            retval.Add(temp);
            last = temp + 1;
        }           
        return retval;
    }

    public static int[] CanonicalForm(string s)
    {
        string table = String.Empty;
        var res = new int[s.Length];
        int marker = 0;
        int lastInd;

        for(int i=0; i < s.Length-1; ++i)
        {
            if (table.Contains(s[i]))
                continue;

            table += s[i];              
            lastInd = i+1;

            if (s.IndexOf(s[i], lastInd) > 0)
                res[i] = ++marker;
            else
                continue;

            foreach (var v in FindIndices(s, s[i], lastInd))
                res[v] = marker;
        }
        return res;
    }

还有比较：

    public static bool ComparePatterns(string s1, string s2)
    {
        return ( (s1.Length == s2.Length) && CanonicalForm(s1).SequenceEqual(CanonicalForm(s2)) );
    }

因此，重点是构建一个规范形式，以便稍后进行比较。这并不特别聪明，但确实可以得出正确的结果。

- avishayp

---

修复了一个错别字，并在第一次实现中添加了另一个检查，禁止将多个字符映射到一个字符上（我想这就是你所说的“不正确”），并指出为什么使用正则表达式做同样的事情是不合理的。 - Martin Ender

Answer 3

只因为我喜欢LINQ :)

void Main()
{
    Console.WriteLine(Map("tree") == Map("loaa"));
    Console.WriteLine(Map("matter") == Map("essare"));
    Console.WriteLine(Map("paper") == Map("mime"));
    Console.WriteLine(Map("acquaintance") == Map("mlswmodqmdlp"));
    Console.WriteLine(Map("tree") == Map("aoaa"));  
}

public string Map(string input)
{
    var seen = new Dictionary<char,int>();
    var index = 0;
    return string.Join(
      string.Empty, 
      input.Select(c =>seen.ContainsKey(c) ? seen[c] : seen[c] = index++));
}

- JerKimball

Answer 4

我不知道如何使用正则表达式来做，但是在代码中，我会逐个字符地遍历两个字符串，一边比较一边构建一个比较列表：

t = l
r = o
e = a
etc.

在添加每个比较之前，我会检查第一个字符串中的字符是否已经存在于列表中。如果第二个字符串对应的字符与比较列表不匹配，则字符串模式不匹配。

- Sid Holland

Answer 5

我刚遇到了同样的问题，然后我写了一段 Python 代码来解决它。这段代码非常简单，不需要导入任何额外的模块。基本思路是将两个给定的字符串分别转换为一个新的模式字符串，利用 ASCII 字符和它们对应的数值之间的关系。最后比较这两个模式字符串。

def SamePattern(s1, s2):
  i = j = 97
  p1 = p2 = ""

  for index1, l1 in enumerate(s1):
    if l1 not in s1[0:index1]:
      p1 += chr(i)
      i += 1
    else:
      p1 += chr(97 + s1.index(l1))

  for index2, l2 in enumerate(s2): 
    if l2 not in s2[0:index2]:
      p2 += chr(j)
      j += 1
    else:
      p2 += chr(97 + s2.index(l2))
      
  if p1 == p2:
    return True
  else:
    return False

- jliu1999