# 用正则表达式匹配3的任意倍数

## 任意DFA转正则表达式的方法

DFA转Regex的核心思想也很简单，逐个删除中间状态(非初始状态和终止状态)，删除过程中把经过这个状态的路径合并到其他路径上，举例如下：

L[p->r] = L[p-q] · star[L[q->q]] · L[q-r]
L[r->p] = L[r-q] · star[L[q->q]] · L[q-p]   

star(L[s,s]) · L[s,f] · star(L[f,s] · star(L[s,s]) · L[s,f] + L[f,f])

# 首先需要把两个状态间的多条边合并成1条
for i = 1 to n:
for j = 1 to n:
if i == j then:
L[i,j] := ε
else:
L[i,j] := ∅
for a in Σ:
if trans(i, a, j):
L[i,j] := L[i,j] + a
remove(k):
for i = 1 to n:
for j = 1 to n:
L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]

# 逐个删除中间状态
for i = 1 to n:
if not(final(i)) and not(initial(i)):
remove(i)

## 代码

public class DFA2regex {
private final static int INITSTATE = 0;
private final static int FINALSTATE = 0;
private final static Set<Integer> set = new HashSet<>();

// 生成DFA时我直接将多条边合并成了一条
private static Map<String, String> getDFA(int n) {
Map<String, List<String>> map = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < 10; k++) {
String key = key(i, j);
if (!map.containsKey(key)) {
}
if ((i*10 + k) % n == j) {
List<String> list = map.get(key);
}
}
}
}
Map<String, String> finalRes = new HashMap<>();
for (HashMap.Entry<String, List<String>> entry : map.entrySet()) {
String key = entry.getKey();
String val =  entry.getValue().stream().reduce("", String::concat);
if (val.length() > 1) {
val = "[" + val + "]";
}
finalRes.put(key, val);
}
return finalRes;
}

private static void remove(int k, int n, Map<String, String> dfa) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (set.contains(i) || set.contains(j)) {
continue;
}
dfa.put(key(i, j), concat(dfa.get(key(i, j)), dfa.get(key(i, k)), star(dfa.get(key(k, k))), dfa.get(key(k, j))));
}
}
}

private static String concat(String s1, String s2, String s3, String s4) {
String str1 = s1;
String str2 = s2 + s3 + s4;
if (str1.length() > 0 && str2.length() > 0) {
str1 += "|";
}
String res = str1 + str2;
if (res.contains("|") || res.contains("*")) {
return "(" + res + ")";
}
return res;
}

private static String star(String s) {
if (s.equals("") || s.equals("|")) {
return "";
}
return s + "*";
}

private static String key(int s, int e) {
return s + "_" + e;
}

public static void main(String[] args) {
int n = 4;
Map<String, String> dfa = getDFA(n);
for (int i = 0; i < n; i++) {
if (INITSTATE != i && FINALSTATE != i) {
remove(i, n, dfa);
}
}

#### 6

^((((([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))))|((((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|(((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))(((([39]|5[39]*[17])|([06]|5[39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([17]|[39][39]*[17])|(4|[39][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((5|[17][39]*[17])|([28]|[17][39]*4)([06]|5[39]*4)*([39]|5[39]*[17]))))*((((4|5[39]*[28])|([06]|5[39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))|((([28]|5[39]*[06])|([06]|5[39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|(([17]|5[39]*5)|([06]|5[39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))((([06]|[39][39]*[06])|(4|[39][39]*4)([06]|5[39]*4)*([28]|5[39]*[06]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*((4|[17][39]*[06])|([28]|[17][39]*4)([06]|5[39]*4)*([28]|5[39]*[06])))*((([28]|[39][39]*[28])|(4|[39][39]*4)([06]|5[39]*4)*(4|5[39]*[28]))|((5|[39][39]*5)|(4|[39][39]*4)([06]|5[39]*4)*([17]|5[39]*5))(([39]|[17][39]*5)|([28]|[17][39]*4)([06]|5[39]*4)*([17]|5[39]*5))*(([06]|[17][39]*[28])|([28]|[17][39]*4)([06]|5[39]*4)*(4|5[39]*[28])))))*\$

## 参考资料

|
9月前
|

26 0
|
3月前
|
Python
Python 内置正则表达式库re的使用

50 3
|
2月前
|

Python网络数据抓取（8）：正则表达式
Python网络数据抓取（8）：正则表达式
24 2
|
2月前
|

Python高级语法与正则表达式(二）

37 2
|
2月前
|

Python高级语法与正则表达式(一）
Python提供了 with 语句的写法，既简单又安全。 文件操作的时候使用with语句可以自动调用关闭文件操作，即使出现异常也会自动关闭文件操作。
30 1
|
2月前
|
Python
Python使用正则表达式分割字符串

25 1
|
2月前
|
Python
Python中re模块的正则表达式
【6月更文挑战第2天】了解Python的re模块，它是处理正则表达式的核心工具。正则表达式用于在文本中查找特定模式。本文讨论了re模块的用法和技巧，包括导入模块、匹配、分组、替换文本、编译正则表达式以及使用预定义字符类、量词、锚点等高级功能。通过实例展示了如何在Python中执行这些操作，帮助提升文本处理能力。掌握这些技巧将使你更有效地利用正则表达式解决字符串处理问题。
25 2
|
2月前
|
Python
Python正则表达式详解：掌握文本匹配的魔法
Python正则表达式详解：掌握文本匹配的魔法
26 0
|
2月前
|
Python
python re 正则表达式库的使用
python re 正则表达式库的使用
19 0
|
2月前
|
Python
python正则表达式入门
python正则表达式入门
22 0