How you define a search of text to find a string A, but exclude results that contains B only (which contains A), but not the both string A and string B?

For example:

  • String A : "Great Wall"
  • String B : "Great Wall of China"
  • Text 1: "The Great Wall"
  • Text 2: "The Great Wall of China"
  • Text 3: "The Great Wall of China is a Great Wall"
  • Text 4: "Lorem Ipsum"

I've used Bold to indicate when String A is present and Italics when String B is present.

We would like to search for Texts that contains A, and A + B, but not B only.

So the results should be the Texts 1 and 3.

What approach would enable us to find these results?

Also, we are using a search that can provide us only a list of items that contains a string.

  • $\begingroup$ So the matching sites of A and B should be non-overlapping? $\endgroup$ – Raphael Nov 8 '17 at 19:47
  • $\begingroup$ It can overlap if both strings are in a same result $\endgroup$ – ceetheman Nov 8 '17 at 20:24
  • 1
    $\begingroup$ Then please give a proper specification of what you want. The example seems to be insufficient. $\endgroup$ – Raphael Nov 8 '17 at 21:25
  • $\begingroup$ How do you find a search string in what system? $\endgroup$ – David Richerby Nov 8 '17 at 22:00
  • 1
    $\begingroup$ What does "A with B" mean? Can you give a precise statement of the problem? $\endgroup$ – D.W. Nov 9 '17 at 2:06

Finite automata to the rescue!


  • $\mathcal{A} = \Sigma^* \cdot \{A\} \cdot \Sigma^*$ and
  • $\mathcal{B} = \Sigma^* \cdot \{B\} \cdot \Sigma^*$

be the regular languages that contain all strings with substring $A$ resp. $B$.

Note then that

$\qquad\displaystyle L = \overline{\mathcal{B}} \cdot \{A\} \cdot \overline{\mathcal{B}} \ \cup\ \mathcal{A} \cdot \mathcal{B} \ \cup\ \mathcal{B} \cdot \mathcal{A}$

is the set of all strings you are looking for, and from basic closure properties of REG we know that it is regular as well.

Constructing a (minimal) DFA from the above description using standard constructions yields an effective method that may or may not be efficient.

  • $\begingroup$ The sets A and B are defined the same way in you answer, but they should be distinct as the string A is a substring of B, but we know search for A will yield results also including B and wants to exclude those containing exclusively B. $\endgroup$ – ceetheman Nov 8 '17 at 20:35
  • $\begingroup$ @ceetheman Typo, my bad. $\endgroup$ – Raphael Nov 8 '17 at 21:25

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