求助:计算一个超长字符串中的子串个数

Question

public int getSubCount(String Content, String Sub)
{
  int Count=0;
  if(Sub.length()!=0){
  Count = Content.length();
  Content = Content.replaceAll(Sub,"");
  Count = Count - Content.length();
  Count = Count / Sub.length();
  }
  ruturn Count;
}

Answer 1

public int getSubCount(String Content, String Sub)
{
   return Content.split(Sub).length-1 ;
}

Answer 2

使用split方法会占用大量内存,AHUA1001(99)的算法我觉得很好,我会进一步进行测试,希望大家能给出更好的建议

Answer 3

public int getSubCount(String content, String sub)
{
  int count=0;
  Matcher m=Pattern.compile(sub).match(content);
  while(m.find()){
    count++;
  }
  ruturn count;
}

Answer 4

Matcher m=Pattern.compile(sub).match(content);
写错了，后面方法应该是matcher
应该是：
Matcher m=Pattern.compile(sub).matcher(content);
或者用
Matcher m=Pattern.matches(sub,content);
效果是一样的。

Answer 5

/*
 * Created on 2006-6-7
 *
 * 
 */
package test;import java.util.regex.Matcher;
import java.util.regex.Pattern;public class StringTest3 {    /**
     * @param args
     */
    public static void main(String[] args) {
        final int n = 10000000;
        
        StringBuffer sb = new StringBuffer(n);
        for(int i=0;i<(n/10);i++){
            sb.append("abcdefghij");            
        }
        
        String s = sb.toString();
        String q = "j";  //子串
        
        
        long t1,t2;
        t1 =  System.currentTimeMillis();
        int l1 = test1(s, q);
        t2 = System.currentTimeMillis();
        System.out.println("1 find count:" + l1 + "\ttime:" + (t2 - t1));
        
        
        t1 =  System.currentTimeMillis();
        int l2 = test2(s, q);
        t2 = System.currentTimeMillis();
        System.out.println("2 find count:" + l2 + "\ttime:" + (t2 - t1));
        
        t1 =  System.currentTimeMillis();
        int l3 = test3(s, q);
        t2 = System.currentTimeMillis();
        System.out.println("3 find count:" + l3 + "\ttime:" + (t2 - t1));
        
        t1 =  System.currentTimeMillis();
        int l4 = test3(s, q);
        t2 = System.currentTimeMillis();
        System.out.println("4 find count:" + l4 + "\ttime:" + (t2 - t1));
    }
    
    public static int test1(String content, String sub){
        int count = 0;
      
        int p = content.indexOf(sub.charAt(0));
        do{
            next:
            if(p > -1){ //查找第一个字符，如果相等则继续比较第二位
                if(p <= (content.length() - sub.length()))
                {
                    for(int j=1;j<sub.length();j++){
                        if(content.charAt(p + j) != sub.charAt(j)){
                            break next;
                        }
                    }
                    count ++;
                }
                else{
                    break;
                }
            }
        
            p = content.indexOf(sub.charAt(0), p + 1);
        }
        while(p > -1);        return count;
    }    public static int test2(String content, String sub){
        int count = 0;
        if (sub.length() != 0) {
            count =content.length();
            content = content.replaceAll(sub, "");
            count = count - content.length();
            count = count / sub.length();
        }
        return count;
    }
 
    
    public static int test3(String Content, String Sub)
    {
       return Content.split(Sub).length-1 ;
    }
    
    public static int test4(String content, String sub)
    {
      int count=0;
      Matcher m=Pattern.compile(sub).matcher(content);
      while(m.find()){
        count++;
      }
      return count;
    }
}

Answer 6

q = "i";1 find count:1000000 time:78
2 find count:1000000 time:1344
3 find count:999999 time:1188
4 find count:999999 time:1062q = "abc"1 find count:1000000 time:94
2 find count:1000000 time:1578
3 find count:1000000 time:1250
4 find count:1000000 time:1172
q = "ja"1 find count:999999 time:63
2 find count:999999 time:1563
3 find count:999999 time:1281
4 find count:999999 time:1172

Answer 7

无论是正则也好，replace也好，其实都是调用charAt来查询、比较、替换，所以直接自己操作来得更快些！