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.