strmatch.java

实现了《算法设计与分析》的一次课后题

import com.sun.org.apache.xpath.internal.operations.Bool;


public class strMatch {

	/**
	 * @param args
	 */
	private int currmat;
	private int maxmat;
	private int minmat;
	private int minlen;
	private String[] s;
	private String[][] f;
	private int match[][][];
	private int[] n;
	
	public static void main(String[] args) {
		

	}
public void search(int len){
	
	int[] p;
	
	if((currmat>maxmat||currmat==maxmat&&len<minlen)&&ok(len)){
		maxmat=currmat;
		minmat=s;
		minlen=len;
	}
	len++;
	if(len==1||s[len-1]!='*'){
		s[len]='?';
		if(check(len))search(len);
		s[len]='*';
		if(check(len))search(len);
	}
	
	for(int i=1;i<=p[len-1];i++){
		s[len]=cha[len-1][i].c;
		if(check(len))search(len);
	}
}

boolean check(int len){
	int i,j,t,k=0;
	currmat=0;
	
	int[] p;
	for(i=1;i<=n[0];i++){
		memset(match[len][i],0,sizeof(match[len][i]));
		if(len==1&&s[1]=='*')match[len][i][0]=1;
		for(j=1;j<f[i].length;j++)
			switch(s[len]){
			case'*':
			   for(t=0;t<=j;t++)
				   if(match[len-1][i][t]==1){match[len][i][j]=1;break;}
			   break;
			case'?':
				match[len][i][j]=match[len-1][i][j-1];
				break;
			default:
				if(s[len]==f[i][j-1])
					match[len][i][j]=match[len-1][i][j-1];
			break;
			}
		for(j=f[i].length;j>=1;j--)
			if(match[len][i][j]==1){
				k++;
				if(j==f[i].length)currmat++;
				break;
			}
	}
	if(k<maxmat||k==maxmat&&len>=minlen)return false;
	p[len]=0;
	for(i=1;i<=n[0];i++)
		for(j=1;j<=f[i].length-1;j++)
			if(match[len][i][j]==1)save(f[i][j],len);
	return true;
}

private boolean ok(int len) {
	int i,j,k,t;
	for(k=1;k<=len;k++)
		for(i=n[0]+1;i<=n[0]+n[1];i++){
		memset(match[k][i],0,sizeof(match[k][i]));
	if(s[1]=='*'&&k==1)match[k][i][0]=1;
	for(j=1;j<=f[i].length;j++)
		switch(s[k]){
		case'*':
			for(t=0;t<=j;t++)
				if(match[k-1][i][t]==1){match[k][i][t]=1;break;}
			break;
		case'?':
			match[k][i][j]=match[k-1][i][j-1];
			break;
			default:
				if(s[k]==f[i][j-1])match[k][i][j]=match[k-1][i][j-1];
			break;
		}
}
	for(i=n[0]+1;i<=n[0]+n[1];i++)
		if(match[len][i][f[i].length]==1)return false;
	return true;
	
}

public void readin()
{
	
		
	
}

private void save(String string, int len) {

	
}

}