Best way to find a specific pattern in a 2D array

I ha开发者_StackOverflow社区ve a 2D array of random characters. I want to match specific patterns of these characters: eg: ABA, BACKA, going up/down/left/right. What is the best algorithm to find this pattern?

If this is like a word-search in that you can only go one direction (once you start left, you can only continue to go left), the answer should be pretty simple, just go ahead and test every possible start location and go each direction. In the worst case this will be O(mn^2) for a n by n If you can go up/left/etc any number of times, the most obvious way is to treat the matrix like a graph and do a BFS or DFS. Depending on the size of the word and the distribution of letters, this may be too costly.

If you had multiple queries for a single matrix, both of these methods could be sped up by caching generated words in a trie-like structure with references to the original cells.