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.


closed as unclear what you're asking by David Richerby, Evil, Tom van der Zanden, Kyle Jones, fade2black Nov 16 '17 at 18:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\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.