Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Would this have been optimized by a compiler?

  1. Nov 19, 2015 #1
    I had a coding interview question that asked to write a function to determine whether one string is a substring of another. So I wrote

    Code (Text):

    public bool IsSubtring ( String s1, String s2 )
    {
        // returns true or false depending on whether s1 is contained in s2
         for ( m = s1.Length, int i = 0, j = (s2.Length - m + 1); i < j; ++i )
         {
                if ( s1 == s2.Substring(i,m) ) return true;
         }
         return false;
    }
     
    I realize that there's a potential performance bug with

    Code (Text):

    s1 == s2.Substring(i,m)
     
    because the entire substring on the right side is returned whereas string comparison only needs pointers/indices. What I'm saying is, if

    Code (Text):

    s1[0] != s2[i]
     
    then the substring doesn't need calculated because we already know there's a mismatch. My procedure has redundant operations.This is unless the compiler doesn't optimize in the way I know it could possibly do. I'm also not aware of anything in the C# standard library that would be the equivalent of

    Code (Text):

    public bool strcmp ( string si, int ia, int ib, string sj, int ja, jb )
    {
         // checks whether the strings si and sj are equal in the range of
         // indices [ia, ib) and [ja, jb) respectively
       
         // ...
    }
     
    which is what I would need in this scenario.

    Does what I'm asking make sense? What are your thoughts?
     
  2. jcsd
  3. Nov 19, 2015 #2
    Also ... I just realized that the problem didn't specificy whether the empty string is defined as contained in the empty string and what do if the strings are null and etcetera. Gotta have all my bases covered.

    Where is Donald Knuth when you need him?
     
  4. Nov 19, 2015 #3
    You just need to use Contains method in C#.

    Code (Text):

    public bool IsSubtring ( String s1, String s2 )
    {
         return s2.Contains(s1);
    }
     
    You are on the right track that you should find the index entry of the pattern in the string and not obtain the substring before comparison. The right hand side expression I think will be calculated first and then == operator will be called. The == operator will again call Equals method to compare each characters available in both the pattern and the acquired substring.
     
  5. Nov 26, 2015 #4

    Svein

    User Avatar
    Science Advisor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook