Sunday算法

第一次自己手撕出来的算法,值得纪念:

class Solution {
    // 特殊情况""的判断以及模式串长过模式串的情况
    public int strStr(String haystack, String needle) {
        if (needle.equals("")) {
            return 0;
        }else {
            if (haystack.equals("") || haystack.length()<needle.length()) {
                return -1;
            }
        }
	// 先将字符串转化为char数组
        char[] str = haystack.toCharArray();
        char[] pat = needle.toCharArray();
        // 初始化模式串和主串的指针
        int i = 0, j = 0,len = pat.length;

        // 因为需要跳出两层循环所以价格flag标志位
        flag:while (i <= str.length - len && j < len) {
            if (str[i + j] == pat[j]) {
                j++;
            }else {
		// 匹配不上就不能让i大于str-pat的长度,否则下标越位
                if (i == str.length - len) {
                    break flag;
                }
		// 循环找s[i+len]
                for (int k = 0; k < len; k++) {
                    if (pat[len - k - 1] == str[i + len]) {
                        i = i + k + 1;
                        j = 0;
                        continue flag;
                    }
                }
                i = i + len + 1;
                j = 0;
            }
        }
        if (j == len) {
            return i;
        }else {
            return -1;
        }
    }
}

自己写起来感觉比KMP简单多了,但这个算法会根据情况有可能复杂度达到mn。

Q.E.D.


刚毕业走上社会被毒打的搬砖狗