字符串模式匹配算法

    技术2022-05-13  0

    字符串模式匹配算法包括三种:蛮力方式,BM模式匹配,KMP模式匹配

     

    蛮力方式容易理解,比较方向从左往右逐个比较,最坏时间复杂度可达O(m·n)(m为 模式字符串长度,n为源字符串长度),最好时间复杂度O(m).

     

    BM模式匹配采用了两个启发式原则:坏字符和好后缀原则,从而避免一些不必要的比较

     

    最坏时间复杂度为O(m·n),最好时间复杂度为O(n/m).

     

    附BM模式匹配代码

     

    /**  * BoyerBoomer算法查找  * @param src 源字符串  * @param dst 模式字符串  * @return int 匹配成功返回1,失败返回0  */ public static int BoyerBoomerMatchPractice(String src,String dst) {  int srclength=src.length();  int dstlength=dst.length();  int s=dstlength-1,d=dstlength-1;  int srcs=dst.length()-1;  while(srcs<=srclength-1)  {//双循环,当循环到源字符串末尾时结束循环   while(d>=0)   {//根据模式字符串进行循环判定    if(src.charAt(s)==dst.charAt(d))    {     s-=1;//若相等从右向左逐步移动一位     d-=1;    }    else    {     int temp=last(dst,src,d,s);//判定移动函数,分为坏字符和最好后缀两种情况     srcs+=temp;     System.out.println("fdsfsdf    " +src.substring(0,srcs)+"  "+temp+" srcs"+srcs);     s=srcs;     d=dstlength-1;     break;    }   }   System.out.println(" "+d);   if(d==-1)    return 1;  }  return 0; }  /**  * 获得移动的步数  * @param dst 模式字符串  * @param src 源字符串  * @param d 模式字符串已匹配的计数  * @param ssss 源字符串中不匹配的计数  * @return 移动的步数  */ public static int last(String dst,String src,int d,int ssss) {  //首先判定是否为坏字符  if(d==dst.length()-1)  {//是   char lastchar=src.charAt(ssss);   System.out.println("lastchar"+lastchar+" "+ssss);   //判定字符是否在模式字符串当中存在   int i;   for(i=0;i<=dst.length()-1;i++)    if(lastchar==dst.charAt(i))     break;   if(i==dst.length())   {    System.out.println(1+"坏字符");    return 1;   }   else    {    System.out.println((d-i)+"坏字符else"+"d "+d+ "i "+i);    return d-i;   }  }          else  {//否,找好后缀    String goodend=dst.substring(d+1,dst.length());//获得好后缀    return isexitst(dst,goodend);     } }  /**  * 当模式字符串当中不存在好后缀时,获得移动的步数  * @param dst 模式字符串  * @param goodend 好后缀  * @return 移动的步数  */ public static int isexitst(String dst,String goodend){  int s=dst.length()-2;//跳过最后一个字符  int ss=dst.length()-2;  int d=goodend.length()-1;  while(s>=d)  {//采用蛮力方式来判断模式字符串当中是否存在好后缀   while(d>=0)   {    if(dst.charAt(s)==goodend.charAt(d))    {     s-=1;     d-=1;    }    else    {     ss-=1;     s=ss;     d=goodend.length()-1;     break;    }    }   if(d==-1)   {    System.out.println("存在好后缀 "+(dst.length()-(s+1+goodend.length())));    return dst.length()-(s+1+goodend.length());   }  }//不存在好后缀  //就寻找最好的最前缀  int dtime=d;  int ds=0;//位置  String sgoodend=goodend;  while(dtime>=0)  {//按照后缀从前往后逐步减一进行判断   if(dst.startsWith(sgoodend)){    System.out.println("最好的最前缀 "+(dst.length()-sgoodend.length()));    return dst.length()-sgoodend.length();}   else   {    ds+=1;    sgoodend=goodend.substring(ds,goodend.length());   }    dtime-=1;  }    return 1; }


    最新回复(0)