Check if two Strings share a common substring in JavaScript

Question

Is there any fast way in JavaScript to find out if 2 Strings contain the same substring? e.g. I have these 2 Strings: "audi is a car" and "audiA8".

As you see the word "audi" is in both strings but we cannot find it out with a simple indexOf or RegExp, because of other characters in both strings.

`if (string1 === string2) { /*identical*/ }` - What are you _really_ trying to ask, how to test whether a particular substring is in two different strings, or whether there exists some substring that appears in two different strings, or...? Could you please show an example _input_ and the desired _output_? — nnnnnn, Oct 22 '12 at 07:14
why do you need indexOf or RegExp? just compare the 2 with '==='. — AMember, Oct 22 '12 at 07:16
If the two strings are `abc` and `cde`, should they be considered "identical" because of `c`? — duri, Oct 22 '12 at 07:16
if you know what the substring is, you can perform indexOf on both the strings to check if the substring exists. — Sandeep G B, Oct 22 '12 at 07:18
@nicmon, I've edited the question to remove a mention of "identical", as that's misleading. If I changed the meaning too much, please edit it to clarify. — Joachim Sauer, Oct 22 '12 at 07:19
I removed the duplicate because that question has nothing to do with this — slebetman, Jun 22 '21 at 18:06
Is this question about finding the [longest common substring](https://en.wikipedia.org/wiki/Longest_common_substring_problem) in two strings? — Anderson Green, Apr 17 '22 at 20:08

score 10 · Answer 1 · answered Oct 22 '12 at 07:50

The standard tool for doing this sort of thing in Bioinformatics is the BLAST program. It is used to compare two fragments of molecules (like DNA or proteins) to find where they align with each other - basically where the two strings (sometimes multi GB in size) share common substrings.

The basic algorithm is simple, just systematically break up one of the strings into pieces and compare the pieces with the other string. A simple implementation would be something like:

// Note: not fully tested, there may be bugs:

function subCompare (needle, haystack, min_substring_length) {

    // Min substring length is optional, if not given or is 0 default to 1:
    min_substring_length = min_substring_length || 1;

    // Search possible substrings from largest to smallest:
    for (var i=needle.length; i>=min_substring_length; i--) {
        for (j=0; j <= (needle.length - i); j++) {
            var substring = needle.substr(j,i);
            var k = haystack.indexOf(substring);
            if (k != -1) {
                return {
                    found : 1,
                    substring : substring,
                    needleIndex : j,
                    haystackIndex : k
                }
            }
        }
    }
    return {
        found : 0
    }
}

You can modify this algorithm to do more fancy searches like ignoring case, fuzzy matching the substring, look for multiple substrings etc. This is just the basic idea.

Very nice function. If you don't mind, I'll [steal](https://github.com/psychowood/ng-torrent-ui/commit/9046410c51859c2964b0d305d3903c1954ec88ef) it. :) — psychowood, Apr 23 '16 at 16:27

score 2 · Answer 2 · answered Oct 22 '12 at 07:18

2

Don't know about any simpler method, but this should work:

if(a.indexOf(substring) != -1 && b.indexOf(substring) != -1) { ... }

where a and b are your strings.

answered Oct 22 '12 at 07:18

techfoobar

65,616
14
114
135

3

But if you still do not know the substring, how could you know before? – Herman Andres Figueroa Feb 10 '19 at 15:51

score 2 · Accepted Answer · edited Mar 21 '19 at 01:39

2

Take a look at the similar text function implementation here. It returns the number of matching chars in both strings.

For your example it would be:

similar_text("audi is a car", "audiA8") // -> 4

which means that strings have 4-char common substring.

edited Mar 21 '19 at 01:39

Serg

6,742
4
36
54

answered Oct 22 '12 at 08:13

dfsq

191,768
25
236
258

score -1 · Answer 4 · answered Oct 22 '12 at 07:34

-1

var a = "audi is a car";
var b = "audiA8";

var chunks = a.split(" ");
var commonsFound = 0;

for (var i = 0; i < chunks.length; i++) {
    if(b.indexOf(chunks[i]) != -1) commonsFound++;
}

alert(commonsFound + " common substrings found.");

answered Oct 22 '12 at 07:34

Shahid

668
8
16

the substrings may have spaces – Herman Andres Figueroa Feb 10 '19 at 15:52

Check if two Strings share a common substring in JavaScript

4 Answers4

Linked