算法 Hw8

1 String matching

1

f = { 0 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 } f=\{0,0,1,2,0,1,2,0,1,2,0,1,2,3,4,5,6,7,8\} f={0,0,1,2,0,1,2,0,1,2,0,1,2,3,4,5,6,7,8}

---

2

$\mid f\ast [q]\mid <q$

当字符串 $P$ 全是相同的字符时，$\mid f\ast [q]\mid =q-1<q$

---

Prefix and suffix tree

1

---

2

---

3

a

后缀树的空间复杂度是 $O(nlogn)$
因为在最坏情况下，每个节点可能需要存储⼀个指向文本的引⽤和⼀些附加信息

b

通过使用引用索引，可以将空间复杂度优化到 $O(n)$。
具体来说，可以通过在每个节点中存储文本的起始位置和长度来引用整个文本，从而避免存储重复的子串。

---

3 Reduction

1

对于每个布尔变量，创建⼀个有向图中的节点，分别表示该变量及其否定形式。
对于每个子句中的文字，创建⼀个有向图中的节点，分别表示该文字及其否定形式。
对于每个子句，创建⼀个大小为 $3$ 的路径，连接对应⽂字的节点。这个路径确保了只能选择其中⼀个文字的赋值。
对于相邻子句中相同的文字，连接它们对应的节点，以确保它们不能同时为真。
连接前⼀步中生成的节点到⽬标顶点 $t$。这样建立⼀个有向图，其中每个布尔变量和每个子句都有对应的节点，而每个可能的布尔赋值都对应于从起始节点 $s$ 到目标节点 $t$ 的⼀条路径。并且，由于每个子句中只能选择⼀个文字为真，所以这些路径是简单路径。 这个转换可以在多项式时间内完成，因此 $3-Sat\le pLongest-Path$