Good news: There's probably a linear time solution to all the versions of the problem presented. Bad news: You have to walk this stable genius through 50 years

Good news: There's probably a linear time solution to all the versions of the problem presented. Bad news: You have to walk this stable genius through 50 years of Suffix Tree and constant time LCA algorithms in 20 minutes.