文字列を正規表現にプログラムで検索しますか？

Question

正規表現を指定すると、その式にプログラムで一致する文字列を見つけることができますか？その場合は、文字列が存在すると仮定して、そのアルゴリズムを記述してください。

ボーナス質問：可能な場合、そのアルゴリズムのパフォーマンス/複雑さを教えてください。

---

PS：注：私はこれに質問していません：Programmatically derive a regular expression from a string。私は予約問題に尋ねている可能性が高いです。

Answer 1

あなたは、このような正規表現を定義すると仮定します

R := 
    <literal string> 
    (RR) -- concatenation 
    (R*) -- kleene star 
    (R|R) -- choice 

次にあなたが一致する文字列が見つかった再帰関数S(r)定義することができます：S(a*(b|c)) = S(a*) + S(b|c) = "" + S(b) = "" + "b" = "b"：たとえば

S(<literal string>) = <literal string> 
S(rs) = S(r) + S(s) 
S(r*) = "" 
S(r|s) = S(r) 

を。

正規表現のより複雑な概念がある場合は、それを基本プリミティブの観点から書き直して、上記を適用することができます。たとえば、R+ = RR*および[abc] = (a|b|c)です。

構文解析された正規表現がある場合（その構文木を知っているので）、上記のアルゴリズムはほとんどの場合、正規表現のサイズが線形であることに注意してください効率的な連結）。

Answer 2

は、このリンクになっていることがあり、あなたにいっぱい助けている： http://www.geeksforgeeks.org/wildcard-character-matching/

http://wiki.tcl.tk/989

Answer 3

Generexは、正規表現の文字列を生成するためのJavaライブラリです。

はそれをチェックアウト：

Generex generex = new Generex("[0-3]([a-c]|[e-g]{1,2})"); 

// Generate random String 
String randomStr = generex.random(); 
System.out.println(randomStr);// a random value from the previous String list 

// generate the second String in lexicographical order that match the given Regex. 
String secondString = generex.getMatchedString(2); 
System.out.println(secondString);// it print '0b' 

// Generate all String that matches the given Regex. 
List<String> matchedStrs = generex.getAllMatchedStrings(); 

// Using Generex iterator 
Iterator iterator = generex.iterator(); 
while (iterator.hasNext()) { 
    System.out.print(iterator.next() + " "); 
} 
// it prints: 
// 0a 0b 0c 0e 0ee 0ef 0eg 0f 0fe 0ff 0fg 0g 0ge 0gf 0gg 
// 1a 1b 1c 1e 1ee 1ef 1eg 1f 1fe 1ff 1fg 1g 1ge 1gf 1gg 
// 2a 2b 2c 2e 2ee 2ef 2eg 2f 2fe 2ff 2fg 2g 2ge 2gf 2gg 
// 3a 3b 3c 3e 3ee 3ef 3eg 3f 3fe 3ff 3fg 3g 3ge 3gf 3gg 

---

もう1：ここではhttps://github.com/mifmif/Generex

は、ライブラリの使用を示すサンプルJavaコードである。ここhttps://code.google.com/archive/p/xeger/

は、ライブラリの使用を示すサンプルJavaコードであります：

String regex = "[ab]{4,6}c"; 
Xeger generator = new Xeger(regex); 
String result = generator.generate(); 
assert result.matches(regex); 

Answer 4

文字列の中でその基準に適合する式を見つけるには、以下のアルゴリズムを試してみました。以下は

i) Create the array for all strings available in given source. 

ii) Create a function with parameters for array, expression and initial index count. 

iii) Call function recursively and increase the index with every move, until we match string has not found. 

iv) Return/break the function if String with desired expression is found. 

同じJavaコードです：私の知る限り、このコードの複雑さを計算した

public class ExpressionAlgo { 

    public static void main(String[] args) { 
     // TODO Auto-generated method stub 

     String data = "A quantifier defines how often an element can occur. The symbols ?, *, + and {} define the quantity of the regular expressions"; 
     regCheck(data.split(" "), "sym", 0); 
    } 

    public static void regCheck(String[] ar, String expresion, int i) { 
       if(ar[i].contains(expresion)){ 
        System.out.println(ar[i]); 
        return; 
       } 

       if(i<ar.length-1){ 
        i=i+1; 
        regCheck(ar, expresion, i); 
       } 
    } 
} 

私は分割を使用していたので、N^3である、方法が含まれており、再帰的にregCheckメソッドを呼び出します。