/**
  * 暴力破解法
  * @param ts 主串
  * @param ps 模式串
  * @return 如果找到，返回在主串中第一个字符出现的下标，否则为-1
  */
 public static int bf(String ts, String ps) {
     char[] t = ts.toCharArray();
     char[] p = ps.toCharArray();
     int i = 0; // 主串的位置
     int j = 0; // 模式串的位置
     while (i < t.length && j < p.length) {
        if (t[i] == p[j]) { // 当两个字符相同，就比较下一个
            i++;
            j++;
        } else {
            i = i - j + 1; // 一旦不匹配，i后退
            j = 0; // j归0
        }
     }
     if (j == p.length) {
        return i - j;
     } else {
        return -1;
     }
 }

/*通过计算返回子串T的next数组。*/
 ？void get_ next ( String T, int *next )
 {
     int i,j;
     i=1;
     j=0;
     next[1]=0;
     while ( i<T[0]) /*此处T[0]表示串T的长度*/
     {
     if (j==0 11 T[i]== T[j]) /* T[i]表示后缀的单个字符，*/
                             /* T[j]表示前缀的单个字符*/
     {
         ++i;
         ++j;
         next[i]=j;
     }
     else
     j= next[j]; /*若字符不相同，则j值回溯*/
     }     
 }

/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。*/
 /* T非空，1SposSStrLength (s)。*/
 int Index KMP (String s, String T, int pos )
 {
     int i= pos;/*i用于主串S当前位置下标值，若pos不为1, */
                 /*则从pos位置开始匹配*/
     int j= 1;   /*j用于子串T中当前位置下标值*/
     int next[255] ; /*定义一next数组*/
     get_ next(T, next); /*对串工作分析，得到next数组*/
     while(i<= S[0] &j<= T[0]) /*若i小于S的长度且j小于T的长度时，*/
                             /*循环继续*/
     {
         if (j==0日1 S[i]== T[j]) /*两字母相等则继续，与朴素算法增加了*/
                                 /*j=0判断*/
         ++i;
         ++j;
         else    /*指针后退重新开始匹配★/
     {
         j = next[j];    /* j退回合适的位置，i值不变*/
     }
     if(j > T[0] )
         return i-T[0] ;
     else
         return 0;
 }