（以下内容仅是提纲，其中的标题包含关系不代表内容包含关系，具体见讲述）
正则表达式
正则表达式的本质
DFA(Deterministic Finite Automaton)，确定有限状态自动机
我们之前在计组上接触的，主要是确定有限状态自动机，可以方便的画出状态转移图
NFA(Nondeterministic Finite Automaton)，非确定有限状态自动机
优点：可以多路径匹配（不确定匹配位置）；缺点：需要回溯，性能差
例：x|xy表达式的NFA表示和DFA表示（上：NFA，下：DFA）
有兴趣的同学可以运用这个网页对比两种自动机（只支持简单正则（复杂正则DFA不一定行
正则表达式的使用
灾难性回溯(catastrophic backtracking)
避免’.’符号，具有专一性
例：找出一个串的前缀，满足其中有五个逗号。
模式串
^(.*,){5}
匹配串（匹配）
1,2,3,4,5,6
扩大一点数据呢？比如5-6$\rightarrow$ 19-20？
模式串
^(.*,){19}
匹配串（仍然匹配）
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
解决方案1：“懒惰”式匹配（尽少匹配）
^(.*?,){19}
改变条件：模式串要求前缀匹配改为要求全串匹配，且最后一个字符要求为逗号：
^(.*?,){5}$
匹配串（非匹配）（注意到20后面没有逗号）
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20
懒惰式匹配结果：
解决方案2：专一性匹配
第一种需求的结果：
^([^,]*,){19}
第二种需求的结果：
^([^,]*,){4}.*,$
独占模式实例（链接的合法性实例，有兴趣的同学可以参阅）
总结：慎重使用懒惰式、独占式、’.’符号，尽量专一匹配、化简匹配。
捕获组
命名和非捕获组
实例：
1
2
3
4
5
6
7
8Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
Pattern p = Pattern.compile("(?:a)(?<name>b)");
Matcher m = p.matcher(s);
m.find();
System.out.println(m.group(0)); // all
System.out.println(m.group("name")); // b
System.out.println(m.group(1)); // b捕获组所需要注意的问题
不 准 套 娃
作业相关
读题
参与WF的形式化表述一定要保证理解正确，不能随意使用未能证明的结论（比如+ - x不合法（其实是合法的））。
数据
构造数据不是随机生成就一定最好。在写一个较复杂的题目之前，先要对数据熟悉，可以手动构造出来一些数据，想一想程序是如何处理这些数据的，这样后面才能写得得心应手。数据的构造见“正确性检查”节。
笔者在写代码前出的数据：
（其中WF表示WRONG FORMAT，可以看到笔者把+- x判做了WF，导致互测翻车）
架构
可以从上到下构造函数，也可以从最基础的部分想起，每个类里分别要实现什么功能，需要和其他的类如何沟通，注意爸爸不要帮孩子写作业。如果想要性能分而且时间足够，可以仔细想想：如何优化？这样的架构能不能应对以后的优化？如果发现当前的架构进行优化需要大量重构，那么就要考虑改变架构了。
上手
根据自己的架构coding~
正确性检查
可以通过手动构造、对拍等方式进行。
这里特别说明：数据构造不是瞎构造，对拍不是万能的。
在数据构造之前，需要对程序进行初步分析：比如你用了BigInteger，且所有的正则表达式中都用了[0-9]+或\\d+等没有特殊处理的方式来匹配数字，那就完全没有必要生成一堆乱七八糟的数字，数字只需要固定为1,0,-1,12,-12这五个数字即可。如果有特判，那么加入特判的数据。如果怕大数出错，还可以来一些大一些的数字，但没必要完全随机，浪费资源且查错效率低。
构造的时候可以使用正则表达式方式生成，也可以手动进行生成，注意测试的情况记录：“有[+-]有空格”，”有[+-]无空格“，甚至记录+和-之间的空格符等等。测过的数据再测试也是资源的浪费。
其实通过这个构造方法，很容易就构造出来把笔者hack掉的数据：+- x。
当然，互测的时候可以随便对拍，因为你也不知道别人会出什么bug（误
优化
然后是优化。考虑各种情况的优化，其实这里的数据一般只能靠自己构造了，比如同类项、数学合并、乘法分配律啊之类的（但一定注意输出要合法）。方法….后面几次可能就看脑洞了（？
对拍
对拍可以稍微随机一些，这个同学已经讲过了就不再赘述了。
互测
不会互测，只会被hack
一个bug被hack五次，太惨痛了.jpg（最后变6次了
放出来供大佬一哂
