## Friday, May 22, 2015

### InfiniteString

Problem:

 TopCoder Problem Statement - InfiniteString Single Round Match 658 Round 1 - Division II, Level One

Overview:

Determine if two strings, when repeated infinitely, are equal.

Java Source:
```     1 public class InfiniteString {
2
3  public String equal(String s, String t) {
4
5   int ptrS = 0;
6   int ptrT = 0;
7
8   /*
9   * Continue looping one character at a time until
10   * we reach both the end of String s and the end
11   * of String t at the same time.
12   */
13   while ((ptrS < s.length()) || (ptrT < t.length()))  {
14
15    /*
16    * If at the end of a String, start over at
17    * the beginning.
18    */
19    ptrS %= s.length();
20    ptrT %= t.length();
21
22    // Return "Not Equal" if characters do not match
23    if (s.charAt(ptrS) != t.charAt(ptrT)) return "Not equal";
24
25    ptrS++;
26    ptrT++;
27   }
28
29   return "Equal";
30  }
31 }
```
Notes:

Imagine creating two Strings s1 and t1 such that s1 = s + s + s ... and t1 = t + t + t + t + ... and the length of both s1 and t1 is equal to the least common multiple of the lengths of s and t.

For example if s = "ababab" and t = "abab", then the length of s is 6, the length of t is 4, and their least common multiple is 12. Therefore, s1 = s + s = "abababababab" and t1 = t + t + t = "abababababab". Since s1 == t1 we should return "Equal"

The important point is that if we step through the Strings s and t one character at a time, and loop back to the beginning of the String when we reach the end; then we can stop when we reach the end of both s and t at the same time. That's the condition that is checked for in the while loop.

The rest is just a matter of checking that the characters match at each position, and incrementing and resetting the pointer to the current character.