Assume I have the following list of companies:

  • Apple
  • Big Apple
  • Google

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.

  • $\begingroup$ 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" $\endgroup$ – John L. Nov 18 '18 at 3:31
  • $\begingroup$ "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? $\endgroup$ – StackOverflowNewbie Nov 18 '18 at 3:39
  • $\begingroup$ 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. $\endgroup$ – John L. Nov 18 '18 at 15:57

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".


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.