3

I'm trying to figure out how to calculate the number of occurrences of a particular string within a group of characters. The catch is that the letters in the string do not need to be next to each other but must appear in sequential order.

For example, the sequence "aabcc" contains four occurences of the string "abc"

aabcc

aabcc

aabcc

aabcc

I thought about using regular expressions, but that only matches the first occurance of the match.

nhahtdh
  • 55,989
  • 15
  • 126
  • 162
Steven Musumeche
  • 2,886
  • 5
  • 33
  • 55
  • 1
    This seems to be an algorithm question rather than a regex question. You can modify a regex engine to count for you, but using a plain regex won't solve your problem. – nhahtdh Jul 16 '15 at 05:19
  • 2
    @Jonny5: Is there a need to post PHP implementation? It's all about algorithm here anyway. – nhahtdh Jul 16 '15 at 09:15

1 Answers1

1

Caveat: this is JavaScript (I'm sorry!). It's also probably way more complicated than it needed to be, but my OCD wouldn't leave it alone.

function search(needle, haystack) {
    var needles = needle.split('');
    var haystacks = haystack.split('');
    var matches = [];
    var nI = 0;
    var hI = 0;
    for (hI = 0; hI < haystacks.length; hI++) {
        for (nI = 0; nI < needles.length; nI++) {
            if (haystacks[hI] === needles[nI]) {
                matches.push(nI);
            } else {
                continue;
            }
        }
    }
    matches = matches.reduce(function (acc, el, index) {
        var cur = acc.map[el];
        if (!cur) {
            acc.map[el] = cur = [];
            acc.res.push(cur);
        }
        cur.push(index);
        return acc;
    }, {
        res: [],
        map: {}
    }).res;
    return matches;
}

function allPossibleCases(arr) {
    return combinations(arr).map(function (combination) {
        return combination.join(" ");
    });
}

function combinations(array) {
    if (!array.length) {
        return [];
    }

    array = array.map(function (item) {
        return item instanceof Array ? item : [item];
    });

    function combine(list) {
        var prefixes, combinations;

        if (list.length === 1) {
            return list[0];
        }
        prefixes = list[0];
        combinations = combine(list.slice(1));
        return prefixes.reduce(function (memo, prefix) {
            return memo.concat(combinations.map(function (combination) {
                return [prefix].concat(combination);
            }))
        }, []);
    }

    return combine(array);
}

var r = allPossibleCases(search("abc", "aabcc"));

// r.length = 4, r = array of matches

Here's a fiddle to play with.

Note: leveraged some code from this answer which counts the remaining objects.

Community
  • 1
  • 1
brandonscript
  • 68,675
  • 32
  • 163
  • 220