串的匹配算法

 

1. 求子串定位函数 :index(String S , String T ,int pos)

       (1) 介绍

              参数介绍 :S 为主串 ,T 为模式串 ,pos 为主串匹配算法遍起始位置 , 如果模式串存在于 主串 S 中的返回索引起始位置 , 否则返回 -1.

         (2) 时间复杂度

              O(n+m)n,m 分别为主串与模式串的长度

       (3) 代码算法

              /**

               * 返回模式串在主串第一次出现的位置

               *

               * @param S 主串

               * @param T 模式串

               * @param pos 主串起始位

               * @return 模式串在主串中的起始位置 , 不存在则返回 - 1

               */

        public int index(String S,String T, int pos) {

           // 起始位置需小于主串的长度

           if (pos >=S.length()) {

                 return  -1;

 

           }

           int i = pos; int j = 0; // 模式串 T 下标记录符

           // 匹配开始

           while (i < S.length()&& j < T.length()) {

               // 循环执行条件为 i,j 不超过主串与模式串数组长度

               if (S.charAt(i) ==T.charAt(j)) {

                  i++;j++;   // 如果匹配完成则 j=T.length() 跳出循环

               } else {

                  // 指针后移

                  i = i - j + 1;j = 0;

               }

           }

           if (j >=T.length())

               return i - j;

           else

               return -1;

        }

       (4) 思考

              如果主串为 aaaaaaaaaaaaaaa...aaaaaaaaaaaaaab, 模式串为 aaaaaaab, 则模式串中有 7  个 a 而主串有 n 个 a, 则每趟比较都出现最后一个字符不相等的情况 , 则指针 i 需要回   溯 n 次 , 效率很低 这时出现了算法时间复杂度最坏的情况 O(n*m), 后面将介绍另外 一种更好的匹配算法 .

2. 求子串定位函数 :KMP 算法

         (1) 介绍

              上述算法最后的思考题可以看出 , 大量的回溯导致了匹配算法的性能被降低了 , 为了   解决这个问题 , 由可 knuth( 克努特 ),morris(莫里斯 ),pratt( 布拉特 ) 同时提出的新算法 解决 , 后人称为 KMP 算法 , 此算法的特点就是在匹配过程中 , 主串指针不会回溯 , 采用 模式串右移 (即遍历模式串当前指针所指的元素的左边部分 ) 的方法 , 以提高算法的 整体效率 .

         (2) 时间复杂度

                   O(n+m)n 为主串的长度 ,m 为模式串长度 ,KMP 算法能确保在 O(n+m) 的数量级上完成 串的模式匹配操作 .

         (3) 代码算法

           /**

             * KMP 算法

             *

             * @param S 主串

             * @param T 模式串

             * @param pos 主串起始位

             * @return 模式串在主串中的起始位置 , 不存在则返回 - 1

             */

        public int index_KMP(StringS, String T, int pos) {

           // 起始位置需小于主串的长度

           if (pos >=S.length()) {

                 return  -1;

 

           }

           int i = pos;

           int j = 0; // 模式串 T 下标记录符

           while (i < S.length()&& j < T.length()) {

               if (j == -1 ||S.charAt(i) == T.charAt(j)) {

                  // j == -1 表示主串下标为 i 时模式串没有与之相等的字符

                  // 所以跳过次字符 ,i++, 并且模式串指向第一个字符从新匹配 ,j++

                  i++;

                  j++;

               } else {

                  // 如果当前主串下标对应字符与模式串当前字符不匹配

                  // 主串不回溯 , 模式串右移 , 即向前遍历模式串的字符查找与当前主 串字符相匹 配的字符

                  // 如果没有找到则返回 -1

                  j = next(j,T, S.charAt(i));

               }

           }

           if (j == T.length())

               return i - j;

           else

               return -1;

        }

       /**

               * 返回与主串指定字符相等的模式串字符位置

               *

               * @param j

               * @param T

               * @param s

               * @return

               */

        public static int next( int j, String T, char s) {

           j -= 1; // 模式串从当前下标位置后一位开始查询与主串指针所指向的元素相 等元素的 位置

           while (j >= 0) {

               if (T.charAt(j) == s){

                  break ;

               }

               j--;

           }

           return j;

        }

3. 两种算法比较

       (1) 测试数据

              StringBuffer strB = new StringBuffer();

       for ( int i = 0; i < 10000000; i++) {

           strB.append( "0" );

       }

       主串 :strB

       模式串 :"000000001"

    (2) 算法代码改进

              在两个比较算法中 , 每进行一次回溯或者移位 , 标记符会 +1, 以此查看移动比较次数 .

         (3) 主函数

              public static void main(Stringargs[]) throws Exception {

           // 计算时间差变量定义

           Date beginDate;

           Date endDate;

           long between;

           SimpleDateFormat sdf= new SimpleDateFormat( "yyyy-MM-dd HH:mm:ss" );

           MyString ms = new MyString();

           StringBuffer strB = new StringBuffer();

           for ( int i = 0; i <10000000; i++) {

               strB.append( "0" );

           }

           strB.append( "1" );

           /* 此时 strB="00000000000...00000001"*/

           beginDate = new Date();

           ms.index(strB.toString(), "00000001" , 0);

           endDate = new Date();

           beginDate =sdf.parse(sdf.format(beginDate).toString());

           endDate =sdf.parse(sdf.format(endDate).toString());

           between =(endDate.getTime() - beginDate.getTime());

           System. out .println( " 基础算法时间差 :" + between);

           beginDate = new Date();

           ms.index_KMP(strB.toString(), "00000001" , 0);

           endDate = new Date();

           beginDate =sdf.parse(sdf.format(beginDate).toString());

           endDate =sdf.parse(sdf.format(endDate).toString());

           between =(endDate.getTime() - beginDate.getTime());

           System. out .println( " 改进后的 KMP 算法时间差 :" + between);

        }

       (4) 结果

           基础算法比较次数 :289999813

       基础算法时间差 :1000

       KMP 算法比较次数 :29999995

       改进后的 KMP 算法时间差 :0

    (5) 结果分析

              因为 KMP 算法所用时在毫秒级之内 , 所以显示为 0, 在比较次数上 , 基础算法所用时整 整多了一个数量级 , 也证明了 KMP 算法的确能很好的提升匹配算法的效率 .

4.JDK-String.indexOf(Str) 原码分析 

       (1) 原码 :

       static int indexOf( char [] source, int sourceOffset, int sourceCount,

                       char [] target, int targetOffset, int targetCount,

                       int fromIndex) {

                // 前三个参数为自身 ( 主串 )String 的 char 数组 , 第一个索引位置 , 字符总数

               // 后三个表示目标 ( 模式串 )

        if (fromIndex >= sourceCount) {

                   // 如果主串索引起始位置 > 主串字符个数

                   // 如果目标字符个数为 0 则返回主串字符总数 , 否则返回 -1

            return (targetCount == 0 ?sourceCount : -1);

        }

        if (fromIndex < 0) {

           // 如果起始主串索引 <0, 则起始索引位置 =0

            fromIndex = 0;

        }

        if (targetCount == 0) {

           // 模式串长度为 0, 返回起始索引位置

            return fromIndex;

        }

                // 模式串第一个匹配字符定义

        char first = target[targetOffset];

          // 最大主串索引位置 , 超出则跳出

        int max = sourceOffset + (sourceCount -targetCount);

        for ( int i = sourceOffset + fromIndex; i <= max;i++) {

            /* Look for first character. */

                    // 查找主串与模式串第一个字符相等的字符位置

            if (source[i] != first) {

                while (++i <= max && source[i] !=first);

            }

            /* Found first character, now look at the rest of v2 */

                   /* 找到第一个字符后如果主串当前索引 <=max 索引位 , 则向后匹配 */

            if (i <= max) {

                // 设置主串匹配开始与结束位

                int j = i + 1;

                int end = j + targetCount - 1;

                // 与模式串匹配

                for ( int k = targetOffset + 1; j < end &&source[j] ==

                         target[k]; j++, k++);

                if (j == end) {

                    /* Found whole string. */

                    return i - sourceOffset;

                }

            }

        }

        return -1;

    }

    (2) 分析 :

              从 JDK 原码来看 ,indexOf(Str) 方法思想上是用的是第一种回溯的匹配算法 , 有兴趣的 朋友也可以读一读 JDK 的原码 .