FilesExpand file tree

 master

/

Code04_AC2.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

125 lines (112 loc) · 3.04 KB

 master

/

Code04_AC2.java

Copy path

Top

File metadata and controls

• Code
• Blame

125 lines (112 loc) · 3.04 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

package class32;

import java.util.ArrayList;

import java.util.LinkedList;

import java.util.List;

import java.util.Queue;

public class Code04_AC2 {

// 前缀树的节点

public static class Node {

// 如果一个node，end为空，不是结尾

// 如果end不为空，表示这个点是某个字符串的结尾，end的值就是这个字符串

public String end;

// 只有在上面的end变量不为空的时候，endUse才有意义

// 表示，这个字符串之前有没有加入过答案

public boolean endUse;

public Node fail;

public Node[] nexts;

public Node() {

endUse = false;

end = null;

fail = null;

nexts = new Node[26];

}

}

public static class ACAutomation {

private Node root;

public ACAutomation() {

root = new Node();

}

public void insert(String s) {

char[] str = s.toCharArray();

Node cur = root;

int index = 0;

for (int i = 0; i < str.length; i++) {

index = str[i] - 'a';

if (cur.nexts[index] == null) {

cur.nexts[index] = new Node();

}

cur = cur.nexts[index];

}

cur.end = s;

}

public void build() {

Queue<Node> queue = new LinkedList<>();

queue.add(root);

Node cur = null;

Node cfail = null;

while (!queue.isEmpty()) {

// 某个父亲，cur

cur = queue.poll();

for (int i = 0; i < 26; i++) { // 所有的路

// cur -> 父亲 i号儿子，必须把i号儿子的fail指针设置好！

if (cur.nexts[i] != null) { // 如果真的有i号儿子

cur.nexts[i].fail = root;

cfail = cur.fail;

while (cfail != null) {

if (cfail.nexts[i] != null) {

cur.nexts[i].fail = cfail.nexts[i];

break;

}

cfail = cfail.fail;

}

queue.add(cur.nexts[i]);

}

}

}

}

// 大文章：content

public List<String> containWords(String content) {

char[] str = content.toCharArray();

Node cur = root;

Node follow = null;

int index = 0;

List<String> ans = new ArrayList<>();

for (int i = 0; i < str.length; i++) {

index = str[i] - 'a'; // 路

// 如果当前字符在这条路上没配出来，就随着fail方向走向下条路径

while (cur.nexts[index] == null && cur != root) {

cur = cur.fail;

}

// 1) 现在来到的路径，是可以继续匹配的

// 2) 现在来到的节点，就是前缀树的根节点

cur = cur.nexts[index] != null ? cur.nexts[index] : root;

follow = cur;

while (follow != root) {

if (follow.endUse) {

break;

}

// 不同的需求，在这一段之间修改

if (follow.end != null) {

ans.add(follow.end);

follow.endUse = true;

}

// 不同的需求，在这一段之间修改

follow = follow.fail;

}

}

return ans;

}

}

public static void main(String[] args) {

ACAutomation ac = new ACAutomation();

ac.insert("dhe");

ac.insert("he");

ac.insert("abcdheks");

// 设置fail指针

ac.build();

List<String> contains = ac.containWords("abcdhekskdjfafhasldkflskdjhwqaeruv");

for (String word : contains) {

System.out.println(word);

}

}

}