Welcome back to the weekly programming contests! If you are new to the contest or need a refresher don’t forget to read up on the rules and information Posted Here
This week’s challenge is to implement java.lang.String’s indexOf(String) method, which returns the index of the first occurrence of the given substring. You should implement the actual algorithm for finding the position of a substring, not use a preexisting method. As the method will not be built into the String class, your method should take in two Strings, the first being the String to search in and the second the substring to find, and return the index as an int.
Also, if you like these weekly programming problems, please make some suggestions for the contest or specific challenges (in the main thread)! This takes time out of my Sunday and its not always fun! Using suggested challenges makes it a lot faster and easier for me.
What about solutions that use methods that in their implementation from String? Pattern.compile(String) uses String#length() and String#codePointAt(int) in its implementation.
I’d say that wouldn’t count. The algorithm should be properly defined but basically you have to write the logic and not just piggy-back onto something that incorporates that logic.
static int indexOf(String a, String b){return r(a,b,0,0);}static int r(String a,String b,int i,int j){return i>=b.length()?j:i>=a.length()?-1:a.charAt(i)==b.charAt(i)?r(a,b,++i,j):r(a.substring(1),b,0,++j);}
Readable:
static int indexOf(String a, String b) {
return indexOf(a, b, 0, 0);
}
static int indexOf(String a, String b, int i, int j) {
if (i >= b.length()) return j;
if (i >= a.length()) return -1;
if (a.charAt(i) == b.charAt(i)) return indexOf(a, b, ++i, j);
return indexOf(a.substring(1), b, 0, ++j);
}
Decided to use no methods other than String#toCharArray().
public static int i(String a,String b){char[]c=a.toCharArray(),d=b.toCharArray();for(int i=-1,j=0;++i<c.length;j=0)try{do if(j==d.length)return i;while(d[j]==c[i+j++]);}finally{}return-1;}
Unminified:
public static int i(String a, String b) {
char[] c = a.toCharArray(), d = b.toCharArray();
for (int i = -1, j = 0; ++i < c.length; j = 0)
try {
do
if (j == d.length) return i;
while (d[j] == c[i + j++]);
} finally {}
return -1;
}
A try statement with no catch clause and an empty finally block is probably something that a compiler could issue a warning for. I don’t have an issue with it, but it’s an example of something that meets the requirements, but is ambiguous as to whether it’s allowed.
It’s also an example of the things code golfers do that we would not normally do because it’s too cryptic or error-prone! Where’s the “do not try this at home” (or, rather, do not attempt while your boss is watching) disclaimer?
public static int i(String a,String b){int l=a.length(),e=b.length(),i=-1,p=0;for(;e<l&&++i<l;p=0)while(p<e&&a.charAt(i+p)==b.charAt(p++))if(p==e)return i;return e>0?-1:0;}
Readable:
// Should work for any charsequence, not just strings :]
public static int indexOf(CharSequence in, CharSequence find)
{
int length = in.length(), end = find.length(), index = -1, pos = 0;
for (;end < length && ++index < in.length(); pos = 0)
{
while(pos < end && in.charAt(index + pos) == find.charAt(pos++))
{
if (pos == end)
{
return index;
}
}
}
return end > 0 ? -1 : 0;
}
Also, jus1in’s squashed down to 164 characters:
public static int i(String a,String b){for(int i=-1,j=0;++i<a.length();j=0)try{do if(j==b.length())return i;while(b.charAt(j)==a.charAt(i+j++));}finally{}return-1;}
