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);
	}
}