This game is a modification to the game of Kayles. Like other impartial games, this problem can be solved using Sprague-Grundy theorem.
Let’s define a game as a substring of S. For convenience, we refer to a substring by its left and right index S(i, j). Note that after a player erases a substring S(a, b), in S(i, j), the game is split into two subgames, S(i, a-1) and S(b+1, j). Because a player can choose any game in his/her turn, the Grundy number of the game is simply the XOR of the Grundy numbers of the two subgames.
Let G(i, j) be the Grundy number of the substring S(i, j). Then G(i, j) = mex({G(i, a-1) XOR G(b+1, j) : S(a, b) exists in the dictionary and is a substring of S(i, j)}
A game is losing iff its Grundy number is zero. So, Teddy, the first player, will win if G(1, |S|) is not zero. On the other hand, Tracy will win if G(1, |S|) is zero.
Interesting to work out how for say “fearchoparchfearchop” and a dictionary of (“fear”, “chop”, “arch”) the starting player needs to take the middle instance of “arch” (of the 3 available) to win.
I don’t see this problem as “Easy”. Needs a bit of structure and theory. Can you explain why the XOR operation works?
Some accepted submissions fail to find Teddy’s winning first move when reducing PAWPAWPAWPAW by the one-word dictionary PAWPAW. I doubt that would be hard to fix for them though, once pointed out.