Complexity of membership testing for finite-regular languages A language $L \subseteq \Sigma^*$ is finite-regular if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Given a finite-regular language $A_L$, am I guaranteed that there exists a polynomial-time algorithm $A_L$ that recognizes $L$?  In other words, I want an algorithm such that on input $x$ it returns true or false according to whether $x \in L$ or not, and the running time is polynomial in the length of $x$.  Is this guaranteed?

Note that the number of states of the complete DFA accepting such $L$ may be $O(|\Sigma|^n)$ so any trivial algorithm actually constructing the full DFA would not be polynomial time. However the number of accepting final states is $O(1)$, which leads me to believe there is some shortcut available here.

Thanks to Yuval Filmus for formalizing this language class, and explaining its closure properties.
Finite-regular languages need not even be decidable. Indeed, if $L$ is any language such that $|L \cap \Sigma^n| \leq C$ for some $C$ independent of $n$, then $L$ is finite-regular (you can show this by considering the case $C=1$). In particular, the language $\{ 1^n : \text{ the $n$th Turing machine halts on the empty input} \}$ is finite-regular but not decidable.