How to find an unknown pattern, that is present in multiple strings?

Question

I'm trying to find a part in multiple strings, that all strings share in common. For example:

const string1 = '.bold[_ngcontent="_kjhafh-asda-qw"] {background:black;}';
const string2 = '[_ngcontent="_kjhafh-asda-qw"] {background-color:hotpink;}';
const string3 = 'div > p > span[_ngcontent="_kjhafh-asda-qw"] {background:hotpink;}'

I don't know in advance what exactly the string is that I'm looking for, so I have to loop over the strings and find out. In the example above, the pattern would be [_ngcontent="_kjhafh-asda-qw"].

Is this even possible? Also, it would have to understand that maybe no such pattern exists. And are there methods for that or do I need to implement such an algorithm myself?

EDIT (context): We are building a validator, that checks a micro-frontend for global CSS rules (not prefixed and outside a shadow-dom), by loading it in isolation in a headless browser (within a jenkins pipeline) and validate, that it should not break any other stuff by global rules, that might be outside the context of the micro-frontend, on the same page. Using a headless browser, we can make use of the document.styleSheets property and not miss any styles that are being loaded. This will find <style> tags and its contents, aswell as content of external stylesheets.

So you're trying to pull out the part of the string between `[` and `]`? If so, use a regex: https://stackoverflow.com/q/1493027/519413 — Rory McCrossan, Nov 11 '22 at 11:29
@RoryMcCrossan OP seems want to find the longest substring that appear in each string — flyingfox, Nov 11 '22 at 11:30
[Longest common substring problem](https://en.wikipedia.org/wiki/Longest_common_substring_problem) — Ouroborus, Nov 11 '22 at 12:15
Does this answer your question? [Find the longest common starting substring in a set of strings](https://stackoverflow.com/questions/1916218/find-the-longest-common-starting-substring-in-a-set-of-strings) — Carsten Massmann, Nov 11 '22 at 13:14

Trentium · Accepted Answer · 2022-11-11T15:04:30.400

Leveraging the BLAST algorithm, the following code snippet seeks successively matching substrings.

//
// See https://stackoverflow.com/questions/13006556/check-if-two-strings-share-a-common-substring-in-javascript/13007065#13007065
// for the following function...
//

String.prototype.subCompare = function(needle, haystack, minLength) {
    var i,j;
    haystack = haystack || this.toLowerCase();
    minLength = minLength || 5;

    for (i=needle.length; i>=minLength; 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
    }
}

//
// Iterate through the array of strings, seeking successive matching substrings...
//

strings = [
  '.bold[_ngcontent="_kjhafh-asda-qw"] {background:black;}',
  '[_ngcontent="_kjhafh-asda-qw"] {background-color:hotpink;}',
  'div > p > span[_ngcontent="_kjhafh-asda-qw"] {background:hotpink;}'
]

check = { found: 1, substring: strings[ 0 ] }
i = 1;
while ( check.found && i < strings.length ) {
  check = check.substring.subCompare( strings[ i++ ] );
}

console.log( check );

Note that without seeing a larger sampling of string data, it's not clear whether this algorithm satisfies the objective...

This is the answer that helped me! I adapted it a bit for my use case and post it as separate answer, but accept yours of course. Thanks a lot! — codepleb, Nov 15 '22 at 12:03

score 1 · Answer 2 · answered Nov 15 '22 at 12:06

Thanks to Trentium's answer, I was able to do it. I adapted the code a little bit, as it was doing too much and also, the substr didn't yield a consistent result (it depended on the order of input strings).

The code could obviously be further minified/simplified.

const findCommonPattern = (base, needle, minLength = 5) => {
  const haystack = base.toLowerCase();

  for (let i = needle.length; i >= minLength; i--) {
    for (let j = 0; j <= needle.length - i; j++) {
      let prefix = needle.substr(j, i);
      let k = haystack.indexOf(prefix);
      if (k !== -1) {
        return {
          found: true,
          prefix,
        };
      }
    }
  }
  return {
    found: false,
  };
};

const checkIfCssIsPrefixed = (strings) => {
  let check = { found: true };

  let matchingStrings = [];

  for (let i = 1; check.found && i < strings.length; ++i) {
    check = findCommonPattern(strings[0], strings[i]);
    matchingStrings.push(check.prefix);
  }

  // Sort by length and take the shortest string, which will be the pattern that all of the strings share in common.
  check.prefix = matchingStrings.sort((a, b) => a.length - b.length)[0];
  return check;
};

console.log(
  checkIfCssIsPrefixed([
    ".spacer[_ngcontent-wdy-c0]",
    "[_nghost-wdy-c0]",
    ".toolbar[_ngcontent-wdy-c0]",
    "p[_ngcontent-wdy-c0]",
    ".spacer[_ngcontent-wdy-c0]",
    ".toolbar[_ngcontent-wdy-c0] img[_ngcontent-wdy-c0]",
    "h1[_ngcontent-wdy-c0], h2[_ngcontent-wdy-c0], h3[_ngcontent-wdy-c0], h4[_ngcontent-wdy-c0], h5[_ngcontent-wdy-c0], h6[_ngcontent-wdy-c0]",
    ".toolbar[_ngcontent-wdy-c0] #twitter-logo[_ngcontent-wdy-c0]",
    ".toolbar[_ngcontent-wdy-c0] #youtube-logo[_ngcontent-wdy-c0]",
    ".toolbar[_ngcontent-wdy-c0] #twitter-logo[_ngcontent-wdy-c0]:hover, .toolbar[_ngcontent-wdy-c0] #youtube-logo[_ngcontent-wdy-c0]:hover",
  ])
);

How to find an unknown pattern, that is present in multiple strings?

2 Answers2