文本中的字符串匹配

关于字符串匹配有很多方法.不过那些方法速度都很慢,最让人受不了的是很多算法比蛮力还要慢.包括kmp算法.上个月读书读到了字符串匹配的书.正好这个月要用.我就写了一个出来.最坏时间复杂度是2n.n表示文本的长度.

匹配的方法是后缀匹配.后缀匹配比前缀比较的次数更少.另外采用滑动的方式.可以精确的跳转.无关的直接跳过.有关的会依次向后滑动.

这个方法是已知的最快方法之一.另外还有位并行什么的用java就太麻烦了.这个用硬件差不多.

搜索文本中字符串的位置.是从0开始的

/**
* 搜索字符串.如果搜索出来返回字母的位置
* -1表示没搜索出来
* @param str表示搜索的字符串
* @param fileContents表示正文
* @return 字符串的初始位置
 * @param start表示从哪里开始.匹配
*/
public int StringExist(String str,String fileContents){
        int start=0;
        return 0;//我承认.java的多态和初始化不会玩.
    }
public int StringExist(String str,String fileContents,int start){
        int flag=-1;
        if(str.length()>fileContents.length()&&start>=fileContents.length()) return flag;
        String temp="";
        int j=start,i=0;
        while(j<fileContents.length()){
        temp="";
        i=0;
        for( ;i<str.length();i++){
            if((j+i)<fileContents.length())
            temp+=fileContents.charAt(j+i);
        }
        //j+=i;
        //System.out.println("j="+j);//测试代码
        int n=jump(str,temp);
        if(n!=0){j+=n;}
        else return j;
        }
        return flag;
    }

下面是跳转的部分

/*
     * 跳转的位置
     * 如果返回是0表示匹配中
     */
    private static int jump(String str,String contentstr){
        if(str.length()>contentstr.length()){return contentstr.length();}
        String str1=reversalString(str);
        String contentstr1=reversalString(contentstr);
        int i=0;
        int flag=str1.length();
        boolean semaphore=true;
        for(i=0;i<str.length();i++)
            if(str1.charAt(i)==contentstr1.charAt(i)&&semaphore==true)
                flag=0;
            else if(str1.charAt(i)==contentstr1.charAt(0)){
                flag=i;
                semaphore=false;
                break;
                }
            else {
                semaphore=false;
                flag=str1.length();
                }


        return flag;
    }

因为是后缀匹配所以要反转字符串

/**
     * 反转字符串
     * @param str->rts
     * @return
     */
    private static String reversalString(String str){
        String str1="";
        for(int i=str.length()-1;i>=0;i--)
            str1+=str.charAt(i);

        return str1;
    }

有了这个就能快速查找文本中是否有指定字符串了.