P3

1.第 183 页，4.1

• \(2*n+2\)元素占用空间的大小为\(676-644=32\)
• 故\(3*n+3\)个元素占用空间的大小为\(32/2*3=48\)
• 故存放的位置为\(644+48=692\)

2.第 184 页，4.9

• 首先计算next数组

• i	0	1	2
  p	a	a	b
  next[i]	-1	0	1

• 进行匹配计算

• ababbaabaa |x aab //向右j=next[1]=0 i++ ababbaabaa x aab //j=0 i++ ababbaabaa |x aab //j=next[1]=0 i++ ababbaabaa | aab //j=0 i++ ababbaabaa | aab //j=0 i++ ababbaabaa ||| aab //找到匹配 return i=5

3.第 184 页，4.10

1. \(D(A(c), B(e), C(a, L(b, c, d)))\)
2. 
3. 
4. \(J1(J2(J1, a, J3(J1)), J3(J1))\)
5. 
6. 

4.第 184 页，4.11

1. head(tail(tail(L1)))
2. head(head(tail(L2)))
3. head(head(tail(tail(head(L3))))
4. head(head(tail(tail(L4))))
5. head(tail(head(L5)))
6. head(head(tail(head(tail(L6)))))

5.计算串ababaabababa的next数组的值

• i	0	1	2	3	4	5	6	7	8	9	10	11
  p	a	b	a	b	a	a	b	a	b	a	b	a
  next[i]	-1	0	0	1	2	3	1	2	3	4	5	4