更改字符串以匹配正則表達式

是否有可能（或爲什麼不可能）將輸入字符串轉換爲匹配正則表達式的字符串的最小Levenshtein距離？更改字符串以匹配正則表達式

即如果1234是字符串和^（[0-9] {6}）$是正則表達式，我需要輸出像123412（輸出字符串匹配的正則表達式和距離原始字符串2的距離，可能有其他字符串但第一個結果會做）

如何做到這一點？（無蠻力..）

編輯：

在其他可能性

，可我只得到Levenshtein距離？（沒有匹配字符串...）

還有什麼其他信息除了表格布爾（匹配或不匹配）可以正則表達式給？

來源

2010-09-12 iamgopal

對我來說似乎很難。我可以想象沒有快速貪婪的算法，這將是一個大搜索。 – LatinSuD 2010-09-12 10:59:16

如果你知道finite automaton你可以構造一個代表你的正則表達式（有庫可以這樣做）。然後你用你的字符串（1234）運行它，你會以某種狀態結束。從這個狀態開始，你做一個breath-first search，直到你達到接受狀態。在搜索過程中，您會記錄您跑過的哪些轉換（字符）。角色會給你最短的（或者其中一個）字符串，這個字符串符合你的正則表達式。

添加鏈接：你可能會對http://www.brics.dk/automaton/看看這是在奧胡斯大學（BSD許可證）

更新實施了自動機庫：我建你尋求從上面的自動機實現的。首先，與其他自動機類處於相同包中的ExtendedOperations類，因爲我需要訪問某些方法。

package dk.brics.automaton; 

public class ExtendedOperations { 
    //Taken from Automaton.run and modified to just return state instead of accept (bool) 
    static State endState(String s, Automaton a) 
    { 
     if (!a.deterministic) a.determinize(); 

     State p = a.initial; 
     for (int i = 0; i < s.length(); i++) { 
      p = p.step(s.charAt(i)); 
      if (q == null) return null; 
     } 
     return p; 
    } 

    public static String getShortestCompletion(Automaton a, String partlyInput) 
    { 
     State e = endState(partlyInput, a); 

     if (e == null) return null; 

     return BasicOperations.getShortestExample(e, true); 
    } 
}

二，一點點testsample：

package subsetautomaton; 

import dk.brics.automaton.*; 

public class Main { 
    public static void main(String[] args) { 
     RegExp re = new RegExp("[a-zA-Z0-9._%+-]+\\@[a-zA-Z0-9.-]+\\.[a-zA-Z]{2,6}"); 
     Automaton a = re.toAutomaton(); 

     System.out.println(ExtendedOperations.getShortestCompletion(a, "a")); 
    } 
}

的例子是一個天真的電子郵件地址寄存器。進出口。請注意，^隱含在註冊表中。進出口。和$一樣。其次，@與\一起轉義，因爲它在此實現中表示「任何字符串」。

以上示例的結果是：@-.AA

來源

2010-09-12 10:53:23

更改字符串以匹配正則表達式

回答

相關問題