Why it is not $O(m)$ but $O(\log m)$?
As a definition, the input size of a problem is the minimum number of bits $(\{0,1\})$ needed to encode the input of the problem. Since it is given that input length $|\sigma|=m$ , you should have $Ceil ( {\log_2 m}) $ bits to encode $\sigma$.