C#

Dewald wrote:

The problem is that the grid can have several thousand entries and a foreach search might take much too long.

public class SearchTree<T> {

	private class UniqueList<Key> : IEnumerable<Key> {

		private Dictionary<Key, byte> _list;

		public UniqueList() {
			_list = new Dictionary<Key, byte>();
		}

		public void Add(Key value) {
			_list[value] = 1;
		}

		public Key[] ToArray() {
			Key[] result = new Key[_list.Count];
			int index = 0;
			foreach (Key value in _list.Keys) {
				result[index++] = value;
			}
			return result;
		}

		public IEnumerator<Key> GetEnumerator() {
			return _list.Keys.GetEnumerator();
		}

		System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
			return _list.Keys.GetEnumerator();
		}

	}

	private class NodeList : Dictionary<char, SearchNode> {

		public new SearchNode this[char c] {
			get {
				SearchNode node;
				if (!this.TryGetValue(c, out node)) {
					node = new SearchNode();
					this.Add(c, node);
				}
				return node;
			}
		}

	}

	private class SearchNode : NodeList {

		private UniqueList<T> _indexes;

		public SearchNode() {
			_indexes = new UniqueList<T>();
		}

		public void Add(string word, int pos, T index) {
			_indexes.Add(index);
			if (pos < word.Length) {
				this[word[pos]].Add(word, pos + 1, index);
			}
		}

		public T[] FindWord(string text) {
			if (text.Length == 0) {
				return _indexes.ToArray();
			} else {
				SearchNode node;
				if (this.TryGetValue(text[0], out node)) {
					return node.FindWord(text.Substring(1));
				}
				return null;
			}
		}

	}

	NodeList _nodes;

	public SearchTree() {
		_nodes = new NodeList();
	}

	public void AddWord(string word, T index) {
		for (int i = 0; i < word.Length; i++) {
			_nodes[word[i]].Add(word, i + 1, index);
		}
	}

	public T[] FindWord(string text) {
		if (text.Length > 0) {
			return _nodes[text[0]].FindWord(text.Substring(1));
		}
		return null;
	}

}

SearchTree<int> tree = new SearchTree<int>();
for (int i = 0; i < lines.Length; i++) {
	foreach (string word in lines[i].Split(' ')) {
		tree.AddWord(word, i);
	}
}

int[] result = tree.FindWord("a");