---

Homework: Overlapping Strings

---

Overlapping strings

• Definition:

  A string s1 overlaps another string s2 if: The characters in some suffix of the string s1 are equal to the characters in the prefix of the string s2 In other words: the last K characters in string s1 is equal to the first K characters in string s2.

  2 strings s1 and s2 can overlap each other in many different ways.

  Consider the strings s1 = "Frodo" and s2 = "odometer".

  The string s1 overlaps the string s2 in the following manners:

  1. Frodo odometer - 0 overlapping character ("trivial" overlap) 2. Frodo odometer - 1 overlapping character 3. Frodo odometer - 3 overlapping characters

  ---

• Maximum overlap:

  The maximum overlap of a string s1 to another string s2 is the longest overlap of s1 to s2.

  The maximum overlap of s1 = "Frodo" on s2 = "odometer" is odo and it has a length equal to 3

  ---

  ---

• Homework assignment

  Write a method maxOverlapLength(s1, s2) in the class Tools that returns an integer that is equal to the length of the maximum overlap of string s1 on string s2

  Example:

  Tools.maxOverlapLength("Frodo", "odometer") returns 3 Tools.maxOverlapLength("Frodo", "od") returns 1 Tools.maxOverlapLength("Frodo", "do") returns 2

  Use this main( ) method to test your work:

  public class MyProg { public static void main(String[] args) { String x1, x2; x1 = "Frodo"; x2 = "odometer"; System.out.println( x1 + " " + x2 + " = " + Tools.maxOverlapLength(x1, x2) ); x1 = "Frodo"; x2 = "Odometer"; System.out.println( x1 + " " + x2 + " = " + Tools.maxOverlapLength(x1, x2) ); x1 = "Frodo"; x2 = "od"; System.out.println( x1 + " " + x2 + " = " + Tools.maxOverlapLength(x1, x2) ); x1 = "Frodo"; x2 = "do"; System.out.println( x1 + " " + x2 + " = " + Tools.maxOverlapLength(x1, x2) ); x1 = "abcabcabc"; x2 = "bcabcxx"; System.out.println( x1 + " " + x2 + " = " + Tools.maxOverlapLength(x1, x2) ); } }

  Hint: use the substring(i, j) to get the parts of the string so you can compare them with the equals() method