For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For…