stringsearch.java

java程序实现的通俗易懂的二分查找的算法源代码

package search;

public class StringSearch
{
	public static int NOT_FOUND=-1;
	public static int SEARCH_CASELESS=1;  //设置大小写是否匹配，初始设置大小写无关
	private static int DELTA_SIZE=65536;  //设定候选字符串使用Unicode;采用ASCII-8为256，使用ASCII-7为128
	
	protected String pattern;
	protected int[] delta;
	protected int search;//存储搜索类型设置参数
	
	//构造函数区
	public StringSearch()
	{
		search=SEARCH_CASELESS;
		pattern=null;
	}
	public StringSearch(String p)
	{
		search=SEARCH_CASELESS;
		setPattern(p);
	}
	
	public StringSearch(final String p,int type)  //自定义大小写无关性
	{
		search=type;
		setPattern(p);
	}
	
	//属性方法
	public  String getPattern()  //返回模式串
	{
		return pattern;
	}
	public  void setPattern(final String p) //设置模式串
	{
		if(search==SEARCH_CASELESS)
			pattern=p.toUpperCase();
		else
			pattern=new String(p);
		
		int n;
		delta=new int[DELTA_SIZE]; 
		for(n=0;n<DELTA_SIZE;++n)      //指定目标串的每个字符的delta值
			delta[n]=pattern.length();
			
		for(n=1;n<pattern.length();++n)  //模式串的delta值得从模式串后不算起的位置
			delta[(int)pattern.charAt(n-1)]=pattern.length()-n;
			
	//	delta[(int)pattern.charAt(pattern.length()-1)]=1;	//此句作用不清楚？
	}
	
	public int getSearchType()  //返回搜索类型
	{
		return search;
	}
	
	public  int getPatternLength()  //返回模式串的长度
	{
		return pattern.length();
	}
	
	//查找算法
	public int find(String target)  //默认从起始位置开始搜索
	{
		return  find(target,0);
	}
    public int find(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[])
	{
		StringSearch tool=new StringSearch("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);
		if(n==-1)
			System.out.println("目标串中不包含模式串");
		else
			System.out.println("模式串在目标串中的起始位置为："+n);
	}
}