Slow two-strings comparer

Question

I have 2 strings for example:

abcabc and bcabca

or

aaaabb and abaaba

I checked that second string is the same or not like first string but shifted. bcabca = ..abca + bc...

using System;
public class TOPSES
{
 static string t1, t2;
 static char[] t1c;
 static char[] t2c;
 static void Main()
 {
 int t;
 t = int.Parse(Console.ReadLine());
 while (t > 0)
 {
 t1 = Console.ReadLine();
 t2 = Console.ReadLine();
 string result = "no";
 t1c = t1.ToCharArray();
 t2c = t2.ToCharArray();
 result = ChangeString(t1c[0], 0);
 Console.WriteLine(result);
 t--;
 }
 }
 public static string ChangeString(char letter, int startIndex)
 {
 int index = t2.IndexOf(letter, startIndex);
 if (index == -1)
 return "no";
 else
 {
 string newString = t2.Remove(0, index);
 newString += t2.Remove(index, t2.Length - index);
 if (t1 != newString)
 return ChangeString(letter, ++index);
 return "yes";
 }
 }
}

How can I improve this code to make it faster? Also, it will be nice if someone could explain what makes this 'program' slow.

• Leonid: I would return a bool true/false instead of "yes"/"no". You should be able to time the bottleneck yourself.
• svick: What makes your program slow? The fact that it has quadratic time complexity and that it creates a lot of garbage.
• WooCaSh: @svick so any idea how to improve this code?
• Leonid: There is a trick to this question stackoverflow.com/questions/2553522/…
• Bobson: @WooCaSh - You forgot the length check. Your code as-is will say that aa is a valid cycling of aabbcc.

Answer 1

This program is organized in a bizarre way.

• t1, t2, t1c, and t2c are static variables, which essentially make them "global" state. This makes your code difficult to follow.
• t2c is a write-only variable — assigned but never used.
• t1c is only barely used — you're only ever interested in the first character.
• It's not obvious what the purpose of ChangeString() is. What are you changing? At first glance, it appears to transform the input (which consists of a single letter and a startIndex) into a "yes"/"no" string.

I would expect the program to follow this outline:

using System;
public class TOPSES
{
 public static void Main()
 {
 for (int t = int.Parse(Console.ReadLine()); t >= 0; t--)
 {
 string s1 = Console.ReadLine(),
 s2 = Console.ReadLine();
 Console.WriteLine(IsRotation(s1, s2) ? "yes" : "no");
 }
 }
 public static bool IsRotation(string s1, string s2)
 {
 ...
 }
}

Notes:

• Main() should be public.
• A for loop gathers all the code related to t together, to make it easy to see what it's for.
• Avoid unnecessarily separating declarations and assignments.

The algorithm you use is also too complicated: you're looking for places in t2 that start with the initial character of t1, then checking if t2, if sliced and reassembled there, matches t1. But why use string.IndexOf(Char, Int) when you could just do string.IndexOf(string)?

public static bool IsRotation(string s1, string s2)
{
 return s1.Length == s2.Length &&
 (s2 + s2).IndexOf(s1) >= 0;
}

This involves just one string concatenation, and no slicing and dicing.

Answer 2

First, as mentioned in the comments, you should return the boolean values true/false instead of the string values "yes"/"no". This should be faster, and is cleaner and more correct.

Second, int.Parse() can be dangerous. Before I read the program and figured out how it worked, I entered the first string, only to have it promptly crash because it expected an integer. The solution to this involves two steps:

1. Inform the user what input is expected
2. Don't let invalid inputs crash the system

I would do this:

int t;
do
{
 Console.WriteLine("Enter the number of pairs to compare: ");
} while (!int.TryParse(Console.ReadLine(), out t));

TryParse() attempts to parse the value and place it in t, and returns a boolean value indicating success of failure.

While I am discussing this section, t is not a very descriptive variable name. A better name would be numPairs, or something that tells what the variable is holding.

Third, you don't need recursion and messy variable handling in the ChangeString() method. In fact, the entire program can be written in a simple loop in a single method:

static bool CompareVals(string a, string b)
{
 if (a.Length != b.Length)
 {
 return false;
 }
 for (int i = 0; i < a.Length; i++)
 {
 a = a.Substring(1) + a[0];
 if (a == b)
 {
 return true;
 }
 }
 return false;
}

This is better because you can pass it two strings from anywhere in your program, instead of having much of the logic in the calling method, and it is faster according to my profiler - it finishes in 6ms with the input "sdfghjkla" and "asdfghjkl", compared to 44ms for your solution. It is also more straight-forward as to what it is doing.

Answer 3

A fastest solution could be something like:

static bool rotCmp(string a, string b) {
 if (a.length != b.length) return false;
 for (int i=0; i < a.length; ++i) {
 for (int j=0; j < b.length && (i+j < a.length ? a[i+j] == b[j] : a[i+j-a.length] == b[j]); ++j);
 if (j == b.length) return true;
 }
 return false;
}