Would this have been optimized by a compiler?

  • #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:
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:
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:
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:
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?
 

Answers and Replies

  • #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?
 
  • #3
156
203
You just need to use Contains method in C#.

Code:
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.
 
  • #4
Svein
Science Advisor
Insights Author
2,124
679

Related Threads on Would this have been optimized by a compiler?

Replies
1
Views
2K
Replies
5
Views
3K
Replies
3
Views
684
  • Last Post
Replies
0
Views
1K
  • Last Post
2
Replies
30
Views
4K
  • Last Post
Replies
1
Views
2K
Replies
25
Views
2K
Replies
25
Views
1K
  • Last Post
Replies
2
Views
3K
Top