15

2つの文字列が同じパターンの繰り返し文字を共有していることを表明する効率的な正規表現はありますか？

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

イベントそれが正規表現を介していない場合、私はタスクを実行するための最も効率的な方法を探しています

4

5 に答える 5

12

最も簡単な方法は、おそらく両方の文字列を同時に手動で調べて、実行中に辞書（対応する文字を一致させる）を作成することです。

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;

同じ方法で、正規表現を作成できます。これは、単一の比較では確かに効率的ではありませんが、将来、1つの繰り返しパターンを複数の文字列に対してチェックする場合に役立つ可能性があります。今回は、キャラクターをそれらの後方参照に関連付けます。

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(.)$。もちろん、この正規表現を少し後で最適化できれば（たとえば、2番目の正規表現の^(.)(.)..\1.(.).\1\3\2$場合）、いずれにせよ、これにより、この1つの特定の繰り返しパターンをチェックする再利用可能な正規表現が得られます。

編集：指定された正規表現ソリューションには注意が必要です。これにより、入力文字列の複数の文字をテスト文字列の1つの文字にマッピングできます（これは、最後の例と矛盾します）。正しい正規表現ソリューションを取得するには、さらに一歩進んで、すでに一致している文字を禁止する必要があります。したがって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の第一人者ではないため、辞書や文字列を作成する際に配列をウォークスルーする際のベストプラクティスではない可能性があります。しかし、それを出発点として使用できることを願っています。

于 2012-11-06T20:00:16.813 に答える
1

正規表現を使用してそれを行う方法はわかりませんが、コードでは、一度に1文字ずつ両方の文字列を実行し、比較しながら比較リストを作成します。

t = l
r = o
e = a
etc.

各比較を追加する前に、最初の文字列の文字がリストにすでに存在するかどうかを確認します。2番目の文字列の対応する文字が比較リストと一致しない場合、文字列パターンは一致しません。

于 2012-11-06T19:58:06.190 に答える
1

編集：受け入れられたコードは正しくなりました。これは代替手段としてここに残ります（これはほとんどの意味であまり良くありません）。

    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)) );
    }

したがって、重要なのは、後で比較できる標準形を作成することです。これは特に賢いわけではありませんが、正しい結果が得られます。

于 2012-11-06T20:57:53.057 に答える
1

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++));
}
于 2012-12-31T23:53:30.597 に答える
0

これと同じ問題に遭遇しました。そして私はそれのためにPythonコードを書きました。かなり簡単で、インポートする追加のモジュールはありません。基本的な考え方は、ASCII文字とそれに対応する数値の関係を使用して、指定された2つの文字列をそれぞれ新しいパターン文字列に変換することです。最後に、2つのパターン文字列を比較します。

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
于 2020-11-05T18:56:48.903 に答える