数据结构(4) - 串

需求 : 在总串S中,查找子串T,若存在,返回子串首字母在总串的索引i.

(1) 暴力查找
    从总串(简称S)的第一个字符S1开始,与子串(简称T)首字母开始比对,S1,S2..,T1,T2...,若相等,返回
    S1,以此类推从S2一直比对到S[s.length-T.length];
    
    分析: 效率低,指针i回溯次数多.
 
(2) KMP查找
    从S[i]开始匹配,T假设从1开始,若一直到T[j]发现出现了不匹配(部分匹配),计算T[j]的next值
    ,然后将T串向右滑动T[j].nextValue位,再次进行比对.若T[j].next=0;则i指针向右移动一位.
    
    分析: 查找效率增大,i指针不回溯;
    
    思想 : 其实,next值得计算是寻找部分匹配子串的中心对称中心,这样的话,在发生不匹配的时候,
    将子串向右滑动nextValue的长度,显然前面还是匹配的,后面再用程序进行判断进行比对就可以了
    i指针并不需要回溯.
    
(3) KMP算法的优化
    可以记录S[i]的值,当滑动完成后,T[nextValue] 的值与S[i]的值相比较,这样就可以先一步判断
    有无向下比对的必要,节省一步操作.

计算 String[] t = {"a","b","a","b","b","c","b","a","b"} 的next数组

    ababbcbab
    
    当在t[0]处不匹配时,t串没有必要向右在滑动了,所以此时S串的指针i向右滑动一位;所以,模式串的
    首位字符的next值一定是0;
    
    在t[1] 处时,中心对称字符是不存在的,所以向右移动一位就可以了,所以,模式串的第二位字符的
    next值一定是1;
    
    在t[j] 时,(j>2)寻找t[0]--->t[j-1] 子串的中心对称点,这样的话,我们将t串向右滑动到中心
    对称点的位置,这个时候,前面已经不需要再比对了,(因为中心对称保证了数据的一致性),再从S[i]
    节点开始比对就可以了.
    
    所以 :
    nextT[] = {0,1,2,1,1,1...}