KMP算法的时间复杂度主要由主串的长度和模式串的长度组成，具体为O(n + m)，其中n为主串长度，m为模式串长度。选项A是正确答案。选项B虽然提到部分匹配表的构建，但并未准确描述时间复杂度的组成。选项C错误，因为字符比较次数并不是直接的复杂度组成部分。选项D错误，字符集大小与时间复杂度无关。