题解 | #矩阵的最小路径和#

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 i=1,j=1;int count=0;
        int []next=new int[S.length()+1];
        get_next(S,next);
       while(j<=T.length())
       {
           
            if(i==0 || S.charAt(i-1)==T.charAt(j-1))
            {
                 if(i==S.length())
                {
                    i=next[i];
                    count++;
                     continue;
                }
                i++;j++;
               
               
            }
           else{
               i=next[i];
           }
       }//while
        return count;
    }//function
    
    void get_next(String T,int []next)
	    {
	    	
	    			
	    	        int plen = T.length();
	    	 
	    	       
	    	 
	    	        next[1] = 0;
	    	 
	    	        next[2]=1;
	    	        int k = 1;
	    	 
	    	        for(int j = 3; j <=plen; j++)
	    	        {
	    	 
	    	                while(k > 0 && T.charAt(j-2) != T.charAt(k-1))
	    	                {
	    	                        k = next[k];
	    	                }
	    	 
	    	                if(k>0&& T.charAt(j-2) == T.charAt(k-1))
	    	                {
	    	                        k++;
	    	                }
	    	                if(k==0) 
	    	                 k++;
	    	                next[j] = k;
	    	              
	    	        }//for
         }//void
}