左神算法与数据结构——基础提升KMP算法-创新互联

解决的问题

• 对于短的str2每个k位置下记录之前前缀与后缀相等的大值

当str1中i位置与str2中0位置开始比较均相等，直至X、Y位置出现第一次不等。按照图示箭头继续比较。

• 由于i1和i1-i2不减，while内语句复杂度为O(2N)

vectorgetNexts(string str) {vectornexts(str.length());
    if (str.length() == 1) {nexts[0] = -1;
        return nexts;
    }
    nexts[0] = -1;
    nexts[1] = 0;
    int cn = 0;
    int i = 2;
    while (i< str.length()) {if (str[i - 1] == str[cn]) {nexts[i++] = ++cn;
        }
        else if (cn >0) {cn = nexts[cn];
        }
        else {nexts[i++] = 0;
        }
    }
    return nexts;
}

int KMP(string str1, string str2) {if (str1.length()< 1 || str2.length()< 1 || str1.length()< str2.length()) {return -1;
    }
    int i1 = 0;
    int i2 = 0;
    vectornexts = getNexts(str2);
    while (i1< str1.length() && i2< str2.length()) {if (str1[i1] == str2[i2]) {i1++;
            i2++;
        }
        else if (nexts[i2] == -1) {i1++;
        }
        else {i2 = nexts[i2];
        }
    }
    return i2 == str2.length() ? i1 - i2 : -1;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧