# Search string excluding longer string containing substring that contains string, not exclusively longer string [closed]

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.

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

Finite automata to the rescue!

Let

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

• 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. – ceetheman Nov 8 '17 at 20:35
• @ceetheman Typo, my bad. – Raphael Nov 8 '17 at 21:25