Why is the Marking Algorithm takes O(number of marks) ?
After mailing the author, I've found the answer:

The marking algorithm can be done in $O(B)$ by making sure that every unit of time we spend produces one mark. Consider the following piece of code:

for i in 1..|T|
  for j in A s.t. T[i]==P[j]
    m[i-j+1]++


The second loop need not take $O(|A|)$, it can be implemented more efficiently by precomputing the matching positions for every character in the alphabet. For example, if $T[i]$ happens to be '$c$' then we precompute all the offsets $j$ in $A$ for which P[j]=='c'. Then every iteration of the second loop produces a mark, like this:

for i in 1..|T|
  for j in offsets[T[i]]
   m[i-j+1]++


The total number of marks is $\sum_{a\in A} F_a=B$ because every position $a\in A$ has $F_a$ marks. So the run time is $O(B)$.