substring and subset method 九章算法

Subtring 现在发展了很多方法但是常用的都是那几种:

(1) Brute Force （暴力破解法）：
      时间复杂度：
     普通 ~NM
     如果souce == target 长度的话，那就是 N(N-M+1)

(2) KMP 算法: 
     时间复杂度： O(M+N)

(3) Boyer-Moore 算法:
     时间复杂度：O(1)


Brute Force 算法设计： 
正所谓暴力破解，那就是逐个对应的关系了。

source : A B A B A
target:   A B A

（1） 首先我们将target 的第一位逐个对应。如果第一位不符合的话，那么将target 的第一位移动到第二位。如此类推。
（2）如果是第一位符合的话，我们就继续用target 对应source 的第二位，第三位，知道target 的长度用完。

如果我们首先思考如果我们都写成两个for loop的话，那么会出现什么问题呢？
那就是当我们每遍历一个source的时候，我们都要遍历完target. 另外会出现溢出的情况。例如source 长度为10，target 长度为3，当指针到了9的时候，指针就会指出source 之外，这里会出现溢出的情况。 

那么我们再考虑两个指针：
进入一个for loop 之后， 我们不需要遍历每个target,只要是第一个target 不相等，我们就可以跳出target循环，然后进入+1的source 循环，那么这里我们这里可以考虑的是判断类语句：
（例如while 和if )

然后最后的条件当target 长度用完，那就是找到字符串。

图（1）

所以我们可以写成：
    public int strStr(String source, String target) {
        //write your code here
        //异常值处理
        if(source == null || target == null ) {
return -1;
}

int n = source.length();
int m = target.length();

for (int i = 0; i <= n - m; i++) {
int j;

                        for(j=0; j < m ; j++) {
if(source.charAt(i + j) != target.charAt(j)) {break;}
}
if (j == m) {
return i;
}
}
        return -1;
    }
}

KMP 算法：
source: BBC ABCDAB ABCDABCDABDE
target:  ABCDABD

(1) 在source 找出第一个匹配的字母。
(2) target+1 进行匹配
(3) 如果不匹配我们就使用这个公式进行移位：
     移动的位置= target 字符算已经移动的位置 - target 字符的部分匹配值，

好像这个字符算： ABCDABD, 我们有AB是相等的，所以部分匹配值为AB（2），这个部分匹配值实在已经移动的字符串的基础上。

所以上面移动了三个位置，但是并没有部分配置值。所以是2-0=2，移动两位。 

Boyer-Moore 算法： 

逆向思维法：

Subsets: