Using FFT to solve pattern matching problem with don't cares
The idea behind the NOT is that $T^c P^R + TP^{Rc}$ is measuring disagreement rather than agreement. Disagreement can come in two ways: text says $0$, pattern says $1$ ($T^c P^R$); and text says $1$, pattern says $0$ ($TP^{Rc}$). That's why you need two summands.

In more detail, $T^cP^R$ measures the number of indices at which the text was $0$ and the pattern was $1$; $TP^{Rc}$ measures the number of indices at which the text was $1$ and the pattern was $0$; and their sum measures the number of indices at which the text and the pattern didn't match.

When the alphabet has size $r$, you can use a similar approach with $r$ summands (an even simpler solution uses $r(r-1)$ summands). I'll let you figure out the details. (No hints will be given, and solutions won't be verified.) Extra points if you manage to do this with the (possibly) optimal $\lceil \log_2 r \rceil$ summands.