boyermoore.java

来自「java程序实现的通俗易懂的二分查找的算法源代码」· Java 代码 · 共 68 行

public class BoyerMoore extends StringSearchTool
{
	protected int[] delta;
	private final static int DELTA_SIZE=65536;
	
	public BoyerMoore()
	{
		super();
	}
	public BoyerMoore(final String p)
	{
		super(p);
	}
	public BoyerMoore(final String p,int type)
	{
		super(p,type);
	}
	
	public synchronized void setPattern(final String p)
	{
		super.setPattern(p);
		int n;
		delta=new int[DELTA_SIZE];
		for(n=0;n<DELTA_SIZE;++n)
			delta[n]=pattern.length();
		for(n=1;n<pattern.length();++n)
			delta[(int)pattern.charAt(n-1)]=pattern.length()-n;
	//	delta[(int)pattern.charAt(pattern.length()-1)]=1;	
	}
	public int find(final String target,int start)
	{
		if((pattern==null)||(start<0))
			return NOT_FOUND;
		String target2;
		if(search==SEARCH_CASELESS)
			target2=target.toUpperCase();
		else
			target2=target;
			
		int t=start+pattern.length();
		while(t<=target2.length())
		{
			int p=pattern.length();
			while(pattern.charAt(p-1)==target2.charAt(t-1))
			{
				if(p>1)
				{
					--p;
					--t;
				}
				else
				{
					return t-1;
				}
			}
			t+=delta[(int)target2.charAt(t-1)];
		}
		return NOT_FOUND;
	}
	public static void main(String args[])
	{
		BoyerMoore tool=new BoyerMoore("napping");
		String strRaven="THE RAVEN\n"+"by Edgar Allen poe\n"+"\n"+"Once upon a midnight dreary,\n"+
		"while i pondered,weak and weary,\n"+"Over many a quaint and curious\n"+"While wnapping,This some vister.";
		int n=tool.find(strRaven);
		System.out.println(n);
	}
}