For a given source string and a target string, you should output thefirstindex(from 0) of target string in source string.
If target does not exist in source, just return-1
.
public int strStr(String source, String target) {
if (target.length() == 0) {
return 0;
}
if (source.length() < target.length()) {
return -1;
}
for(int i = 0; i <= source.length() - target.length(); i++){
int j;
for(j = 0; j < target.length(); j++){
if(source.charAt(i + j) != target.charAt(j)){
break;
}
}
if(j == target.length()){
return i;
}
}
return -1;
}
Robin Karp: 利用hash
public int strStr2(String source, String target) {
if(source == null || target == null || source.length() < target.length()){
return -1;
}
if(target.length() == 0){
return 0;
}
int key = 0, base = 10000000, power = 1, lock = 0;
for(int i = 0; i < target.length(); i++){
key = (key * 31 + target.charAt(i)) % base;
power = (power * 31) % base;
}
// power /= 31;
for(int i = 0; i < source.length(); i++){
lock = (lock * 31 + source.charAt(i)) % base;
if(i >= target.length()){
lock -= source.charAt(i - target.length()) * power % base;
if(lock < 0){
lock += base;
}
if(lock == key && source.substring(i - target.length() + 1, i + 1).equals(target)){
return i - target.length() + 1;
}
}
}
return -1;
}