I am looking for familiar problems on strings of finite length over an finite alphabet, where a polynomial time algorithm is known.
To be more precise, let $\Sigma$ be a finite alphabet. I am looking for problems, where the input (or an important part of the input) is a set (or an ordered list) of strings $w_1,\dots ,w_m\in\Sigma^*$ (gladly $m=1$) and there are known algorithms to solve the problem in polynomial time in the length of the input strings (+ possible other input variables). It would be great to get references to the algorithms, too.
Given a nondeterministic finite automaton $M$ with $s$ states, which accepts the regular language $T(M)$ and a string $w\in\Sigma^n$. Is $w\in T (M)$? Obviously, this is possible in polynomial time in $n $ (and $s $).
Why do I want to know such problems?
I want to analyse, whether the polynomial time holds for some (possibly exponential) compressed representations of the strings in the length of the compact form or not.
I am interested in problems of all possible areas. It is also okay to post just one problem. I hope to get a bunch of interesting problems in addition.
Thanks a lot!