昨天在博客园看到一道关于字符串匹配的题，用BM算法实现了一下，有不足之处望大家多提意见！题目是这样的，找出一个字符串中某子串出现的次数，直接上代码：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81 |
import java.util.Scanner;public class BM_Test { public
static void main(String args[]){ Scanner s=new
Scanner(System.in); System.out.println("请输入文本串"); String str1=s.next(); System.out.println("请输入要查找的字符串"); String str2=s.next(); int
length=str2.length(); int[] matchJump=new
int[length]; char[] p=str2.toCharArray(); int
count=0; computeMatchJumps(p,length,matchJump); int
start1=0; int
start2=0; for(int
i=start1;i<str1.length();i++){ int
num=i; for(int
j=0;j<str2.length();j++){ if(str1.substring(num,num+1).equals(str2.substring(j,j+1))){ num++; if(j==str2.length()-1){ start1+=str2.length(); count++; continue; } else continue; } if(!str1.substring(num,num+1).equals(str2.substring(j,j+1))){ start1+=matchJump[j]; break; } } } System.out.println(count); } public
static void computeMatchJumps(char[] p,int
m,int[] matchJump){ int
low; int
shift; int[] sufx = new
int[m+1]; for(int
k=0;k<m;k++){ matchJump[k]=m+1; } sufx[m]=m+1; for(int
k=m-1;k>=0;k--){ int
s=sufx[k+1]; while(s<=m){ if(p[k]==p[s-1]){ break; } matchJump[s-1] = min(matchJump[s-1],s-k-1); s=sufx[s]; } sufx[k]=s-1; } low=1; shift=sufx[0]; while(shift<=m){ for(int
k=low;k<=shift;k++){ matchJump[k-1]=min(matchJump[k-1],shift); } low=shift+1; shift=sufx[shift]; } for(int
k=0;k<m;k++){ matchJump[k]+=m-k; } } private
static int min(int i, int j) { // TODO Auto-generated method stub int
minNum=i<j?i:j; return
minNum; } } |
原文：http://www.cnblogs.com/yinhutaxue/p/3555382.html