In this talk I will be discussing the MNRS quantum random walk
technique introduced by Magniez et al.[1] and discussing an
example of its application on the longest common substring problem. The
applications on string problems was introduced and discussed by Akmal
and Jin.[2] They show that the longest common substring
problem can be solved by a quantum algorithm in time
[1]: Frederic Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha. "On the hitting times of quantum versus random walks". SODA 2009, pp. 86–95. Algorithmica 63: 91–116, 2012. arXiv:0808.0084
[2]: Shyan Akmal and Ce Jin. "Near-optimal quantum algorithms for string problems". SODA 2022, pp. 2791–2832. arXiv:2110.09696.