学步园

  最近临近毕业，准备走人，闲来刷下题。挺有意思的字符串题目，先Trie后DFS。将模式串组成Trie，然后上面跑DFS。

  易错的地方几个（惭愧地参考了别人的心得才发现），模式串有可能有一模一样的，所以DFS时必须都找出来。

import java.util.*;

public class Main {
	
	public static void main(String[] args)
	{
		Scanner scan  = new Scanner(System.in);
		Trie trie = new Trie();
		
		int m,n;
		m = scan.nextInt();
		n = scan.nextInt();
		
		for(int i=0;i<m;i++)
		{
			String tmpStr = scan.next();
			trie.Insert(tmpStr, i);
		}
		
		for(int i=0;i<n;i++)
		{
			String tmpStr= scan.next();
			Node cNode = trie.root;
			ArrayList<Integer> ids = new ArrayList<Integer>();
			
			trie.DFSSearch(cNode, tmpStr, 0, ids);
			
			if(ids.size() == 0)
			{
				System.out.println("Not match");
			}
			else
			{
				Collections.sort(ids);
				int prev = -1;
				for(int j=0;j<ids.size();j++)
				{
					if(ids.get(j) == prev)
					{
						continue;
					}
					System.out.print(ids.get(j) + " ");
					prev = ids.get(j);
				}
				System.out.print('\n');
			}
		}
		
	}

}

class Node{

	ArrayList<Integer> sIds;
	Node[] children;
	
	public Node()
	{
		sIds = new ArrayList<Integer>();
		children = new Node[28];
	}
}

class Trie
{
	public Node root;
	
	public Trie()
	{
		root = new Node();
	}
	
	public void Insert(String str, int iStrId)
	{
		int iStrPos = 0;
		Node cNode = root;
		while(iStrPos < str.length())
		{
			int iCPos;
			if(str.charAt(iStrPos) == '*')
				iCPos = 26;
			else if(str.charAt(iStrPos) == '?')
				iCPos = 27;
			else
				iCPos = str.charAt(iStrPos) - 'a';
			
			if(cNode.children[iCPos] == null)
			{
				cNode.children[iCPos] = new Node();
			}
			cNode = cNode.children[iCPos];
			iStrPos++;
		}
		cNode.sIds.add(iStrId);
	}
	
	
	public void DFSSearch(Node cNode, String str, int iStrPos, ArrayList<Integer> answerIds)
	{
		if(iStrPos == str.length())
		{//Finish Matching, output the answer.
			SearchAnswer(cNode, answerIds);
			return;
		}
		
		else 
		{//Go on matching.
			if (cNode.children[str.charAt(iStrPos) - 'a'] != null) {
				// Match
				DFSSearch(cNode.children[str.charAt(iStrPos) - 'a'], str,
						iStrPos + 1, answerIds);
			}
			
			if (cNode.children[27] != null) {
				// Match
				DFSSearch(cNode.children[27], str, iStrPos + 1, answerIds);
			}
			
			if (cNode.children[26] != null) {
				/*下面两行注释掉的代码是个易错点，特别第二行，因为如果对于每一个树节点，如果不往下走，无法知道上一个对应的字符串序号。
				 * 这样子讲很抽象，举个例子。比如有两个pattern 
				 * 1:*
				 * 2:?
				 * 给定字符串w。跑出来结果你就知道啥问题了。**/
				// Ignore
				//DFSSearch(cNode.children[26], str, iStrPos, answerIds);
				// Match
				//DFSSearch(cNode, str, iStrPos + 1, answerIds);
				
				for(int i=iStrPos; i<=str.length();i++)
				{
					DFSSearch(cNode.children[26],str,i,answerIds);
				}
				
			}
		}
	}
	
	public void SearchAnswer(Node cNode, ArrayList<Integer> ids)
	{
		for(int i=0;i<cNode.sIds.size();i++)
		{
			ids.add(cNode.sIds.get(i));
		}
		
		if(cNode.children[26] != null)
		{
			SearchAnswer(cNode.children[26], ids);
		}
		
	}
}