Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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...

Here is code it works but too slow:

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";
        }
    }
}


Question:

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


Thanks Leonid for source!

Code look now that:

using System;
using System.Linq;

public class TOPSES
{
    static void Main()
    {
        string t1, t2;
        int t;
        t = int.Parse(Console.ReadLine());

        while (t > 0)
        {
            t1 = Console.ReadLine();
            t2 = Console.ReadLine();

            string result = "no";

            if ((t1 + t1).IndexOf(t2) != -1)
                result = "yes";

            Console.WriteLine(result);
            t--;
        }
    }
}
share|improve this question
2  
I would return a bool true/false instead of "yes"/"no". You should be able to time the bottleneck yourself. –  Leonid Feb 25 '13 at 0:22
    
What makes your program slow? The fact that it has quadratic time complexity and that it creates a lot of garbage. –  svick Feb 25 '13 at 0:36
    
@svick so any idea how to improve this code? –  WooCaSh Feb 25 '13 at 0:57
2  
There is a trick to this question stackoverflow.com/questions/2553522/… –  Leonid Feb 25 '13 at 3:17
1  
@WooCaSh - You forgot the length check. Your code as-is will say that aa is a valid cycling of aabbcc. –  Bobson Feb 25 '13 at 16:06

1 Answer 1

up vote 4 down vote accepted

Less is more! So, here is a shorter/cleaner version (not tested):

namespace MyNamespace
{
    using System;

    public class StringExtension
    {
        public static bool IsRotationOf(this string lhs, string rhs)
        {
            return (lhs.Length == rhs.Length) && (lhs+lhs).Contains(rhs));
        }
    }

    public class TestRotation
    {
        public static int Main(string[] args)
        {
            int numTries = Int32.Parse(Console.ReadLine());
            for (int tryIndex = 0; tryIndex < numTries; ++numTries)
            {
                string lhs = Console.ReadLine();
                string rhs = Console.ReadLine();
                bool isRotation = lhs.IsRotationOf(rhs);
                Console.WriteLine(isRotation ? "yes" : "no");
            }

            return 0;
        }
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.