Regexを単語の中のRegexのグループを見つけるために

Question

単語内の正規表現のすべての組み合わせを検出する正規表現を生成する方法を知りたい。たとえば："MAKE"ため

マッチだから、これらすべての可能な値のための正規表現は問題がある[A-Za-z]+

ある"M", "MA", "MAK", "MAKE", "AKE", "AK", "A", "KE, "K", "E"

を返す必要があり、どのように私は、単一の単語から可能なすべての値を取得行います

Regex regex = new Regex("[A-Za-z]+"); 
foreach(Match m in regex.Matches(word)) 
{ 
    for(int i = 0; i < m.Groups.Count; i++) 
     Console.WriteLine(m.Groups[i].Value); 
} 

私は「MAKE」のみを取得しますが、この単語内のすべての一致をグループ化したいと思います。

Answer 1

私はRegexでString substrings generatorのアプローチをしようとしていました。 アイデアはありましたが、それほど明確ではありませんでしたが、最終的にアプローチがありました。それほど多くはテストされていませんが、今では可変サイズの不明な単語に対して可能なすべての部分文字列（左から右へ）を作成します。

これはC＃Regexエンジンで動作します。ベンチマークも複雑さも計算していない（O（N^2）のように見える？）。

私は数時間前にマイクロソフトインタビューで与えられた問題に対して、別のアプローチをしたいと思っていました。ポイントは、対角線、水平および垂直（左から右、上から下）のNサイズのNワード（この例ではサイズ4のワード4つ）のマトリックス内のすべての可能な単語を見つけることでした。

static void CheckWords(String[] words, HashSet<String> valid) 
    { 
     //Horizontal 
     foreach(var w in words) 
      FindWords(w, valid); 

     //Vertical 
     String word = ""; 
     for(int i = 0; i < words.Length; i++) 
     { 
      for(int j = 0; j < words[i].Length; j++) 
       word += words[j][i]; 

      FindWords(word, valid); 
      word = ""; 
     } 

     //Diagonal 
     String word2 = ""; 
     for(int i = 0, j = 0; i < words.Length; i++, j++) 
     { 
      word += words[i][j]; 
      word2 += words[i][words[i].Length - i - 1]; 
     } 

     FindWords(word, valid); 
     FindWords(word2, valid); 

    } 

    static void FindWords(String word, HashSet<string> valid) 
    { 
     int len = word.Length; 
     //Generate all possible (left to right) substring for String with Length - a [ FOr example, for "MAKE" we can have possible values for "MAKE", "MAK", "MA", "M", "AKE", "KE", "K, "E", "A 
     for(int a = 0; a < len; a++) 
     { 
      //Find all possible substring with this length { k = 1, k = 2, k = 3, ..., k = word.Length } 
      for(int k = 1; k <= word.Length; k++) 
      { 
       Match match = new Regex(@"([A-Za-z]{" + k + "}){1}").Match(word); 
       //For all found groups, we just care for the first group wich contains the main unrepeated substrings 
       for(int i = 0; i < match.Groups.Count - 1; i++) 
        for(int j = 0; j < match.Groups[i].Captures.Count; j++) //Check each permutation for each word with K length. You can Console.Write each value to check it's generated string 
         if(valid.Contains(match.Groups[i].Captures[j].Value)) 
          Console.WriteLine(match.Groups[i].Captures[j].Value); 
      } 
      word = word.Substring(1, word.Length - 1); 
     } 
    } 

だから、この入力を与えられた：

HashSet<String> words = new HashSet<string>(); 
    words.Add("MAKE"); 
    words.Add("MAD");   
    words.Add("END"); 
    words.Add("MINE");     

    String[] array = { "MAKE", "IEMY", "NIAH", "ENDN" }; 

    CheckWords(array, words); 

は、辞書内の配列内のすべての4つの単語を見つける必要があります。

Answer 2

与えられた単語を使用して正規表現を構築するためのプログラム的な方法があります

((((M)(?=(((A)K)E))A)(?=((K)E))K)(?=(E))E)

このようにあなたはそれを行うことができます。
私はこの正規表現を手作業で作った方法です。 私はそれを展開するための練習として残します。

** Grp 0 - (pos 0 : len 4) 
MAKE 
** Grp 1 - (pos 0 : len 4) 
MAKE 
** Grp 2 - (pos 0 : len 3) 
MAK 
** Grp 3 - (pos 0 : len 2) 
MA 
** Grp 4 - (pos 0 : len 1) 
M 
** Grp 5 - (pos 1 : len 3) 
AKE 
** Grp 6 - (pos 1 : len 2) 
AK 
** Grp 7 - (pos 1 : len 1) 
A 
** Grp 8 - (pos 2 : len 2) 
KE 
** Grp 9 - (pos 2 : len 1) 
K 
** Grp 10 - (pos 3 : len 1) 
E 

フォーマットされ、血みどろの詳細：

(       # (1 start) 
     (       # (2 start) 
      (       # (3 start) 
       (M)       # (4) 
       (?= 
        (       # (5 start) 
          (       # (6 start) 
           (A)       # (7) 
           K 
         )        # (6 end) 
          E 
        )        # (5 end) 
       ) 
       A 
      )        # (3 end) 
      (?= 
       (       # (8 start) 
        (K)       # (9) 
        E 
       )        # (8 end) 
      ) 
      K 
    )        # (2 end) 
     (?= 
      (E)       # (10) 
    ) 
     E 
)        # (1 end) 

Answer 3

あなただけの "MAKE" のすべての連続したサブストリングにマッチする正規表現を必要とする場合は、以下を使用することができます。

^(M(|A(|K(|E)))|A(|K(|E))|K(|E)|E)$ 

文字列の先頭と末尾に気にしない場合は、次のように短縮できます。

M(|A(|K(|E)))|A(|K(|E)|K(|E)|E