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

results matching ""

    No results matching ""