Algorithm-problem/SuffixAutomaton.java at master · Elvins/Algorithm-problem · GitHub

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
package com.NCBICrawler.crawler;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * 后缀自动机，用于LCS
 *
 * @author Elvins
 *
 */
public class SuffixAutomaton {

	Node root, last, cnt;
	int size;

	SuffixAutomaton() {
		root = new Node(0, null);
		last = root;
		size = 1;
	}

	void expend(char c) {
		size++;
		cnt = new Node();
		cnt.len = last.len + 1;
		Node p;
		for (p = last; p != null && !p.trans.containsKey(c); p = p.pre) {
			p.trans.put(c, cnt);
		}
		if (p == null) {
			cnt.pre = root;
		} else {
			Node q = p.trans.get(c);
			if (q.len == (p.len + 1)) {
				cnt.pre = q;
			} else {
				size++;
				Node clone = new Node();
				clone.len = p.len + 1;
				clone.pre = q.pre;
				// map深度复制
				for (Iterator<Character> keyIt = q.trans.keySet().iterator(); keyIt.hasNext();) {
					Character key = keyIt.next();
					clone.trans.put(key, q.trans.get(key));
				}

				for (; p != null && p.trans.get(c) == q; p = p.pre) {
					p.trans.put(c, clone);
				}
				q.pre = cnt.pre = clone;
			}
		}
		last = cnt;
	}

	void build(String s) {
		int l = s.length();
		for (int i = 0; i < l; i++) {
			expend(s.charAt(i));
		}
	}

	int findLCS(String s) {
		int ans = 0, len = s.length(), t = 0;
		Node now = root;
		for (int i = 0; i < len; i++) {
			char x = s.charAt(i);
			if (now.trans.containsKey(x)) {
				now = now.trans.get(x);
				t++;
			} else {
				while (now != null && !now.trans.containsKey(x)) {
					now = now.pre;
				}
				if (now == null) {
					now = root;
					t = 0;
				} else {
					t = now.len + 1;
					now = now.trans.get(x);
				}
			}
			ans = ans > t ? ans : t;
		}
		return ans;
	}

}

class Node {
	Map<Character, Node> trans;
	Node pre;
	int len;

	Node() {
		this.len = 0;
		this.pre = null;
		trans = new HashMap<Character, Node>();
	}

	Node(int len, Node pre) {
		this.len = len;
		this.pre = pre;
		trans = new HashMap<Character, Node>();
	}
}