You could do the Regex in SPARQL as you suggested, performance implications will vary on the subset of items at the moment it is fired.
An example from a SPARQL query using that approach ("Look for all teams in the second league of the bundesliga"):
SELECT distinct ?team ?label
?team dbp-ont:league ?league .
?league rdfs:label ?league_label .
?team rdfs:label ?label .
FILTER regex(str(?league_label), "bundesliga","i") .
FILTER regex(str(?league_label), "2","i") .
FILTER(lang(?label) = "en") .
See the results for this query in FactForge
But for high performance in larger sets of unfiltered data I do not think this is what you're looking for. For enterprise free text search take a look at Jena and at this related question: Do you use full-text search with SPARQL? If so how and why?.