# String Search - how to find the "most" accurate string?

Assume I have the following list of companies:

• Apple
• Big Apple

Then I have this sample string:

Big Apple is a company that is trying to be the next Google.

Given the list of companies and the sample string above, how can I find the list of companies in the sample string?

If I iterate through the list of companies and search for it in the sample string, I would find three matches: Apple (because "Apple" exist in "Big Apple"), Big Apple, and Google. In my scenario, I wouldn't want just Apple to match since Big Apple is a more accurate match.

I'm trying to implement the solution in PHP, but a general description/strategy on how to solve this would be helpful.

• Welcome to Computer Science! The first thing we should have is a clear definition of the most accurate string for a match. How about the following criteria? Substring $S$ is said to be prefered to substring $T$ if and only $S$ is longer than $T$ or, if it is as long as $T$, it appears earlier. A substring is called matched if it matches a company name. A substring will be counted as a match if and only if it is a matched substring and no matched substring intersecting it is prefered to it. In other words, only matched and maximally prefered substrings will be counted as "most accurate strings" Nov 18 '18 at 3:31
• "or, if it is as long as T, it appears earlier" -- the reliance on sorting order could be a potential flaw? Your definition seems right, I think. How do I solve? Nov 18 '18 at 3:39
• Are you really concerned about performance? If not, then you can just sort the given list of company names by length. Iterate through each position of the sample string. For each position, try matching the company names from the longest to shortest. Once matched, removed that matched substring. Nov 18 '18 at 15:57
• @JohnL. I think your definition might be a bit too 'strict' for this scenario. Consider this example: $S = abcd$ and the companies $\{abc, cd, d\}$. Your definition would only consider $\{abc\}$ in the solution, but OP would prefer $\{abc, d\}$ to be the answer, I believe. Apr 12 '20 at 1:41
• Instead I propose this slight variant: Substring $S$ is said to be preferred to substring $T$ if and only if $S$ is longer than $T$ or, if it is as long as $T$, it appears earlier. A substring is called matched if it matches a company name. A set of matched substrings is called a Feasible Set if every pair of substrings in it is disjoint. Now, consider any two Feasible Sets. Order each of them internally by the "preferred" total order, with the most preferred substrings at the beginning. The Feasible Set which is 'lexicographically more preferred' is the more preferred Feasible Set of the two. Apr 12 '20 at 1:49

One way to do so is as follows:

1. Sort the company names from longest to shortest.
2. For each company name $$c$$:

a. Find all the substrings of the input string that equal $$c$$ and don't use any characters from a previous occurrence of a company name.

b. If some substring exists, add $$c$$ to the solution.

This strategy works if you're trying to solve the problem you've stated. But if you want a more robust solution, you should look into using natural language processing tools like Python's NLTK. These tools allow you to take syntax and context into account, and might help you tell the difference between "I ate a big apple", and "I bought shares in Big Apple".

• This doesn't fully solve the problem, IMO. Suppose there are multiple occurrences of $c$, which one do you choose? Choosing all of them would lead to unnecessarily having to discard some other future company names. Choosing any one of those occurrences arbitrarily would also not work as one occurrence might block a more preferred company name in the future than another one, and so you'd want to avoid choosing that. But the obvious greedy solution that this leads to, "Pick the occurrence such that picking it blocks the smallest future company name", also doesn't work. Apr 12 '20 at 1:58
• That greedy doesn't work because there might have been another occurrence which blocks a more preferred company name in the future, but the blockage of that future company name might have been inevitable because of some other company name that you'd choose in between these two. And once you take this inevitability into consideration, the preference between the occurrences might change. And so on - you can take this down a deep rabbit hole. Apr 12 '20 at 2:02