字符串匹配

BF,KMP,BM

先不说这些，java里都有哪些实现呢？

 1 package yxy;
 2 
 3 import java.util.regex.Pattern;
 4 
 5 /**
 6  * @author crane
 7  * 字符串匹配
 8  */
 9 public class ZiFuChuanPiPei {
10 
11     public static void main(String[] args) {
12         // TODO Auto-generated method stub
13         String str="I'm crane";
14         String subStr1="crane";
15         String subStr2="hello";
16         System.out.println("str : "+str);
17         System.out.println("subStr1 : "+subStr1);
18         System.out.println("subStr2 : "+subStr2);
19         //方法1 boolean contains(CharSequence s) 当且仅当此字符串包含指定的 char 值序列时，返回 true
20         System.out.println("str.contains(subStr1) : "+str.contains(subStr1));   
21         System.out.println("str.contains(subStr2) : "+str.contains(subStr2));
22         //方法2 int indexOf(String str) 返回指定子字符串在此字符串中第一次出现处的索引
23         System.out.println("str.indexOf(subStr1) : "+str.indexOf(subStr1));   
24         System.out.println("str.indexOf(subStr2) : "+str.indexOf(subStr2));
25         //方法3 boolean matches(String regex)  告知此字符串是否匹配给定的正则表达式
26         String regex1=".*"+subStr1+".*";
27         String regex2=".*"+subStr2+".*";
28         System.out.println("str.matches(regex1) : "+str.matches(regex1));
29         System.out.println("str.matches(regex2) : "+str.matches(regex2));
30         //方法四  java.util.regex包中提供的类 使用方法查看JDK API
31         System.out.println("Pattern.matches(regex1, str) : "+Pattern.matches(regex1, str));//注意：这里是regex而不是String
32         System.out.println("Pattern.matches(regex2, str) : "+Pattern.matches(regex2, str));
33     }
34 
35 }

View Code

运行结果：

str : I'm crane
subStr1 : crane
subStr2 : hello
str.contains(subStr1) : true
str.contains(subStr2) : false
str.indexOf(subStr1) : 4
str.indexOf(subStr2) : -1
str.matches(regex1) : true
str.matches(regex2) : false
Pattern.matches(regex1, str) : true
Pattern.matches(regex2, str) : false

View Code

查看JDK1.6的源码发现（我在eclipse中安装了jd-eclipse插件，反编译用的，查看源码很方便的）

  public boolean contains(CharSequence paramCharSequence)
  {
    return indexOf(paramCharSequence.toString()) > -1;
  }

即contains调用了indexOf

 1 package yxy;
 2 
 3 import java.util.regex.Pattern;
 4 
 5 /**
 6  * @author crane
 7  * 字符串匹配
 8  */
 9 public class ZiFuChuanPiPei {
10 
11     //BF
12     static boolean isMatch(char[] text,char[] pattern){
13         if(text==null||pattern==null)
14             return false;
15         int tLength=text.length,pLength=pattern.length;
16         if(tLength<pLength)
17             return false;
18         int i=0,j=0,k=0;    //i,j分别指向文本和模式比较时的字符下标，k记录文本比较时开始的下标，便于回退
19         while(i<=tLength-pLength){    //这个不好想的话，想象pattern的长度为1，就容易理解了
20             k=i;
21             //while(pattern[j]==text[i]&&j<pLength){    
22             //j<pLength是因为不能比较pattern的结束符,额，C语言里边是那样，java 里面是吗？
23             //http://blog.csdn.net/easy_gemini/article/details/8226123 
24             while(i<=tLength-pLength&&j<pLength&&pattern[j]==text[i]){
25                 j++;
26                 i++;
27             }
28             if(j==pLength){
29                 return true;
30             }else{    //回溯
31                 j=0;
32                 i=k+1;
33             }
34         }
35         return false;
36     }
37     
38     static boolean isMatch(String text,String pattern){
39         if(text==null||pattern==null)
40             return false;
41         int tLength=text.length(),pLength=pattern.length();
42         if(tLength<pLength)
43             return false;
44         int i=0,j=0,k=0;    //i,j分别指向文本和模式比较时的字符下标，k记录文本比较时开始的下标，便于回退
45         while(i<=tLength-pLength){    //这个不好想的话，想象pattern的长度为1，就容易理解了
46             k=i;
47             //while(pattern[j]==text[i]&&j<pLength){    
48             //j<pLength是因为不能比较pattern的结束符,额，C语言里边是那样，java 里面是吗？
49             //http://blog.csdn.net/easy_gemini/article/details/8226123 
50             while(i<=tLength-pLength&&j<pLength&&pattern.charAt(j)==text.charAt(i)){
51                 j++;
52                 i++;
53             }
54             if(j==pLength){
55                 return true;
56             }else{    //回溯
57                 j=0;
58                 i=k+1;
59             }
60         }
61         return false;
62     }
63     
64     public static void main(String[] args) {
65         // TODO Auto-generated method stub
66         String text="I'm crane";
67         String pattern1="crane";
68         String pattern2="hello";
69         System.out.println(isMatch(text.toCharArray(),pattern1.toCharArray()));
70         System.out.println(isMatch(text.toCharArray(),pattern2.toCharArray()));
71         System.out.println(isMatch(text,pattern1));
72         System.out.println(isMatch(text,pattern2));
73     }
74 
75 }

运行结果：

false
false
false
false

代码不对，错在24行和50行的

i<=tLength-pLength

这样的话，没次到这里就不再继续比较了，所以不对

改为：i<tLength 就对了。