Char_sequence

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        // write code here
        int count = 0 ;

        int[] next = getNextArr(S);
        int pre = 0 ;
        ////遍历主串和模式串
        for(int sufix =0 ; sufix < T.length();sufix++){
            //只要不相等，回退到next数组记录的下一位
            while(pre > 0 && T.charAt(sufix) != S.charAt(pre)){
                pre = next[pre-1];
            }
            if(T.charAt(sufix)==S.charAt(pre)){
                pre++;
            }
            // 说明完全匹配一次 ; 计数加一，索引回退到next数组记录的下一位
            if(pre==S.length()){
                count++;
                pre=next[pre-1];
            }

        }
        return count ;
    }

    public int[] getNextArr(String s){
        int[] next = new int[s.length()];
        next[0] = 0 ;
        for(int sufix = 1,pre=0 ; sufix < s.length() ; sufix++){
            // //只要不相等，回退到next数组记录的下一位
           while(pre > 0 && s.charAt(pre) != s.charAt(sufix)){
                pre = next[sufix -1];
           }
            //前缀索引后移
           if(s.charAt(sufix) == s.charAt(pre)){
               pre++;
           }
            //确定应该回退到的下一个索引
            next[sufix] = pre ;

        }


        return next;
    }
}