i need to search for a pattern match in an array of strings, where each string is a list of symbols and a given string in the array may match to only one symbol in the pattern.

So suppose we have a pattern as A+B*C and we have the string array as

[1] ACD

[2] BC

[3] ADE

[4] BAE

[5] CD

[6] DE

So above we have a match starting from string [3], as AAC (or ABC). i need to find the longest such match.

i think of one approach as to construct strings taking different combination of symbols (one from each string) and compare it against the pattern.

So starting form 1st string ("ACD") we take up A and match it against the pattern. it is a partial match so we go ahead and take B from second string ("BC"). So we now have "AB" which is a partial match. So we go ahead to string 3 ("ADE") and try each of its symbols for a partial match. But it fails so we drop the current path and try again taking different symbol from the first string, and so on. i think matcher.hitEnd() can help in detecting partial match.

While this approach may work, it will be inefficient for large number of strings (and symbols). i have such strings numbering in thousands (taken from a database table). It will be great if some one can point out more efficient approach to this.