Counting substrings that belong to a regular language
You can do it in $O(|x|\cdot |M|)$ with dynamic programming.
Let $q_0$ be the starting state, $\delta$ the transition function of $M$, and $a(q) \to \{0, 1\}$ a boolean function indicating whether $q$ is an accepting state in $M$.
Let $A[i, q]$ be the number of non-empty prefixes of $x_ix_{i+1}\ldots x_n$ accepted by $M$ if we start in state $q$. We can directly compute $A[n, q] = a(\delta(q, x_n))$. Then, going backwards row by row, we can fill the table using $A[i,q] = a(\delta(q, x_{i})) + A[i+1, \delta(q, x_{i})]$.
Finally, you sum $a(q_0) +\sum_{i=1}^nA[i, q_0]$ as your answer, as this is the sum over all non-empty prefixes of all non-empty suffixes, plus one if the empty string is accepted, thus all substrings.