There would be way to many combinations for my to partial strings table.
It isn't anywhere near as bad as it sounds at first.
You won't want it case sensitive so you are are only looking for 70 characters even if you include all punctuation, space and special characters.
The choice of the number of characters in the partial strings stored is a trade off. The more characters in the substring the more unique combinations that need to be stored but the less the number of records in the join table.
Taking the simplest as an example (the two character substring) there are only 4900 possible two character sequences with 70 different characters.
The process begins by finding all entries that include the first two characters of the search string. The crudest implimentation then checks characters 2 and 3, then 3 and 4 and so on. Only the records which match all those results are possible matches to the full search string.
Using three character substring will vastly reduce the number of matches and only increase the maximum number of substring records to 343K even if every possible combination existed. The real figure will be much less.
There will be many false positives but after a few iterations the whole test string can be applied to the reduced result set. How many iterations depends on the number of character in the record being searched.
An improved algorith stores the substring position in the join table and uses this to determine matches much more quickly. In the case of the two character window it looks at (1,2);(3,4) etc and analyses the character positions returned for the appropriate sequence spacing.
The database index can be used so the searches are very fast and a very small number of iterations will quickly reduce the possible matches.
Feed algorithm that into a Stored Procedure and you have a very rapid search that is potentially capable of matching in the OnChange event of the search box depending on the number of users and the grunt available at the server.