ac自动机 C++多条件比较

AC自动机主要用于字符串匹配，多条件比较的话可以在AC自动机中添加多个模式串，并在匹配时同时匹配多个条件。例如，可以将多个关键字或多个正则表达式作为模式串，同时匹配多个条件。

具体实现可以参考以下步骤：

1. 将多个模式串添加到AC自动机中，每个模式串对应一个状态节点。

2. 在每个状态节点中，添加一个列表，用于存储与该节点匹配的所有模式串。

3. 在匹配时，对于每个输入字符，从当前状态节点开始，按照AC自动机的匹配规则进行匹配，同时将与匹配的模式串存储在状态节点中的列表中。

4. 匹配完成后，遍历所有匹配成功的状态节点，取出其列表中的模式串，并进行多条件比较。

例如，假设有三个关键字："apple"、"banana"、"orange"，需要同时匹配两个条件：长度大于等于5且以"a"开头。则AC自动机的构建和匹配流程如下：

构建AC自动机：

1. 将三个关键字添加到AC自动机中，得到以下状态图：

0 -a-> 1 -p-> 2 -p-> 3 -l-> 4 -e-> 5 ($"apple")
0 -b-> 6 -a-> 7 -n-> 8 -a-> 9 -n-> 10 -a-> 11 ($"banana")
0 -o-> 12 -r-> 13 -a-> 14 -n-> 15 -g-> 16 -e-> 17 ($"orange")

2. 在每个状态节点中添加一个列表，用于存储与该节点匹配的模式串。

0: []
1: []
2: []
3: []
4: []
5: ["apple"]
6: []
7: []
8: []
9: []
10: []
11: ["banana"]
12: []
13: []
14: []
15: []
16: []
17: ["orange"]

匹配：

假设输入字符串为"an apple a day keeps the doctor away"，则匹配流程如下：

1. 从状态0开始，输入字符"a"，到达状态1。

2. 输入字符"n"，到达状态8。

3. 输入字符" "，到达状态0。

4. 输入字符"a"，到达状态1。

5. 输入字符"p"，到达状态2，并将模式串"apple"存储在状态5的列表中。

6. 输入字符"p"，到达状态3。

7. 输入字符"l"，到达状态4。

8. 输入字符"e"，到达状态5，并将模式串"apple"存储在状态5的列表中。

9. 输入字符" "，到达状态0。

10. 输入字符"a"，到达状态1。

11. 输入字符"d"，到达状态0。

12. 输入字符"a"，到达状态1。

13. 输入字符"y"，到达状态0。

14. 输入字符" "，到达状态0。

15. 输入字符"k"，到达状态0。

16. 输入字符"e"，到达状态0。

17. 输入字符"e"，到达状态0。

18. 输入字符"p"，到达状态0。

19. 输入字符"s"，到达状态0。

20. 输入字符" "，到达状态0。

21. 输入字符"t"，到达状态0。

22. 输入字符"h"，到达状态0。

23. 输入字符"e"，到达状态0。

24. 输入字符" "，到达状态0。

25. 输入字符"d"，到达状态0。

26. 输入字符"o"，到达状态0。

27. 输入字符"c"，到达状态0。

28. 输入字符"t"，到达状态0。

29. 输入字符"o"，到达状态0。

30. 输入字符"r"，到达状态0。

31. 输入字符" "，到达状态0。

32. 输入字符"a"，到达状态1。

33. 输入字符"w"，到达状态0。

匹配完成后，遍历状态5、11、17的列表，取出模式串"apple"和"orange"，然后进行长度和开头字母的判断。符合条件的模式串为"apple"，因为它的长度大于等于5且以"a"开头。