According to my CS knowledge so far, a lexer uses DFA(which takes linear time) for 'each' token type to find the next token, so in the worst case, it should try 'all possible' token types of a language. (there are some other reasons, e.g. to find the 'longest matching pattern' to distinguish between
if a(keyword) and
Then, the lexer repeats this process until the input string ends, producing N tokens as a result. So I ended up with the conclusion that lexer has $\mathcal O(n^2)$ time complexity. But every resource and book says lexer takes linear time because the DFA has linear time complexity. What I am missing?
*Edit: What was wrong is that I assumed the lexer uses multiple DFAs for each token. In reality, the lexer forms a single DFA to represent all token types in a given regular language, and it can identify token types with it's final states. Thus it takes $\mathcal O(n)$.