2つの文字列が同じパターンの繰り返し文字を共有しているかどうか確認してください。

Question

2つの文字列が同じパターンの繰り返し文字を共有すると主張する効率的なRegexはありますか？それは正規表現を通じてない場合

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

イベント、私は正規表現を使用してどのように行うのか分からないが、コードで、私は実行しますタスク

Answer 1

あなたはそれをやっている間、最も簡単な方法は、（それは、対応する文字をmatces）を同時に手動で両方の文字列を歩くと辞書を構築することが考えられます：

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回の比較では効率的ではありませんが、将来、複数の文字列に対して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つの特定の繰り返しパターンをチェックする再利用可能な正規表現が得られます。

EDIT：与えられた正規表現ソリューションには警告があります。入力文字列の複数の文字をテスト文字列の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の教祖ではないので、辞書や文字列を構築する際の配列を歩くのにはベストプラクティスではないかもしれません。しかし、私はあなたが出発点としてそれを使用できることを願っています。

Answer 2

を実行するための最も効率的な方法を探しています両方の文字列を1文字ずつ、私が行くように比較し、比較リストを作成を通じて：

t = l 
r = o 
e = a 
etc. 

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

Answer 3

編集：承認済みのコードが正しくなりました。これは代替手段として残っています（これはほとんどの意味ではあまり良くありません）。

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

だから、ポイントは、後で比較できる標準的なフォームを構築することです。これは特にスマートではありませんが、正しい結果が得られます。

Answer 4

だけ私はLINQを愛しているから。（ "木"、 "aoaa"）=>真：:)

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