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.An example: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!
Polynomial time algorithms on strings
strings;polynomial time;data compression