Counting the number of patterns that exist in a particular string

Question

I am solving this problem where the function returns the number of times a pattern is found in a said string word. It could be easily solved via std::find but I wanted to implement the logic myself and see if I bring in some improvements but turns out my solution fares worst than with std::find.

The solution works but I am wondering if it could be improved upon. The current time complexity I reckon is O(N*M) where N = elems of pattern, M = elems of word.

// Sample input
pattern: ["a","abc","bc","d"]
word:    "abc"

// Sample output
3

bool isSubstr(string word, string pattern)
{
    int wordIdx = 0;
    int pattIdx = 0;
    size_t pattSz = pattern.size();
    
    for (int i=0; i<word.size(); i++)
    { 
        int curI = i;
        
        // iterate over word as long as each letter matches with pattern's
        while (i < word.size() && pattern[pattIdx] == word[i])
        {
            pattIdx++;
            i++;
        } 
        
        // ... we have found a pattern
        if (pattIdx == pattSz)
        {
            return true;
        }
 
        // a full pattern wasn't found but a part of it was. Reset the i
        if (i != curI)
        {
            pattIdx = 0;
            i = curI;
        }
    }
    return false;
}

int containsSubStr(vector<string>& patterns, string word) 
{
    int count = 0;
    
    for (auto& pattern : patterns)
    {
        if (isSubstr(word, pattern))
        {
            count++;
        }
    }
    return count;
}

p.s: I understand the importance of prefixing the containers with std:: but this is not a production code and rather merely an interview question

Answer 1

The current time complexity I reckon is O(N*M) where N = elems of pattern, M = elems of word.

I'd say O(NM) where N = the total size (sum of lengths) of patterns, M = length of word. There is a strong dependence on the sizes of the patterns, each individual isSubstr can take as much as O(word.length * pattern.length), when sufficiently unlucky.

There are other options, such as:

• Use KMP for the substring search, with time complexity O(word.length + pattern.length).
• Use Boyer-Moore for the substring search, which is back to O(word.length * pattern.length) in the worst case, but in many cases it's much better, even taking Ω(word.length / pattern.length) time at best.
• Build a suffix array (with LCP) for word in O(word.length), then you can use binary search to implement isSubstr in O(pattern.length + log(word.length)). This is substantially different than the previous two, which both depended mostly on the length of word, while this time the time a substring search takes depends mostly on the length of the pattern being searched for and almost not at all on the length of word (the logarithm of a size is always small). On the other hand, there is O(word.length) preprocessing now, and it's a relatively "slow" O(word.length).
• Replace the whole thing with a version of Aho-Corasick, a specialized "search many substrings in a string" algorithm. This relies on preprocessing all the patterns, representing the whole set of them with a finite state machine.

std::find

Shouldn't that be std::string.find? std::find could find a character in a string, but if you used it to search for a substring then I don't know how you did it.

(Admittedly slim) chance of accessing the pattern out-of-bounds

In this loop,

// iterate over word as long as each letter matches with pattern's
while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
}

Usually pattern[pattern.size()] yields the null character while the corresponding character in word is typically not the null character, so the loop stops, and pattern would not be accessed out-of-bounds. But that relies on word not containing embedded null characters, and an std::string can contain embedded null characters. A string that is meant to be text probably won't (and shouldn't) contain them though. So it's possible to go out of bounds there, but with the intended usage it shouldn't happen, and I wouldn't really call this a bug .. but something to think about.

Answer 2

Harold gave a good answer addressing the algorithm used. I'll look at other aspects of your code.

You say you have a using namespace std; somewhere because you're writing interview code. In an interview, be sure to make clear whether you're writing "demonstration" code (focus on algorithms) or "production" code (focus on maintainability). It's easy enough to talk about this in traditional face-to-face interviews, but many companies are turning to pre-interview screening, where you need to ensure that your choices are mentioned in your code comments.

Another good thing to mention in an interview is why you've not taken different approaches (in the question you implied you'd use std::find() in production code; I'd also consider creating a regular expression that matches all the patterns simultaneously).

I would also expect some clarification about how you've interpreted the requirements - what you have implemented returns the number of patterns which match the string, but another interpretation would be how many substrings are matches for one or more of the patterns. (This might just be ambiguity in your paraphrasing - I note the question title and description differ on the most likely intention). You'll want to say something about how you handle repeated patterns and overlapping matches.

The interface you've provided is something I'd ask about if I were interviewing you. Look at these:

bool isSubstr(std::string word, std::string pattern);

int containsSubStr(std::vector<std::string>& patterns, std::string word);

This is quite constrictive - we only accept very specific types. We make copies of the string arguments, and we allow the function to modify the vector argument.

Instead of passing string objects, I would prefer to see std::string_view objects used (again, a comment could mention how your production code differs from demonstration code, and would alleviate my concerns as an interviewer).

bool isSubstr(std::string_view word, std::string_view pattern);

int containsSubStr(const std::vector<std::string>& patterns,
                   std::string_view word);

I might go further, and allow passing other containers of patterns:

template<std::ranges::range Collection>
    requires std::convertible_to<typename Collection::value_type, std::string_view>
int containsSubStr(const Collection& patterns, std::string_view word);

I might make it even more general, by templating on the string character type as well, if I wanted to impress the interviewer. Or at least mention my reasons for not doing so.

The naming is perhaps misleading. containsSubStr() reads like a predicate function, but actually returns a count of patterns that match. When I'm interviewing, one thing I want to see is good communication skills, and choosing good names is very much part of that.

Answer 3

Simplify the loop logic

The nested loop in isSubstr is a bit difficult to understand:

• The outer loop variable i can be modified at multiple places. It's simplest when the counter is only modified in the loop statement (i++ in this example).

• It's confusing that the inner loop repeats the i < word.size() condition that's also in the outer loop statement, and yet there is no (explicit) condition on pattern.size(), which intuitively should be important.

The logic would be cleaner using the following algorithm:

• For each index start in the input string from 0 to word.size() - pattern.size() + 1. The idea here is that near the end of the word when there are not enough characters to match the pattern, stop the loop.
  • For each index in the pattern
    • If word[start + index] != pattern[index] then break out of this inner loop, and continue in the outer loop at start + 1
  • If the end of the inner loop is reached without ever braking out, then a match was found, return true immediately
• If the end of the outer loop is reached, then there was no match, return false

Putting that into code:

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto start = 0; start < word.size() - pattern.size() + 1; start++)
    { 
        bool found = true;
        for (auto i = 0; i < pattern.size(); i++)
        {
            if (word[start + i] != pattern[i])
            {
                found = false;
                break;
            }
        }
        if (found)
        {
            return true;
        }
    }
    return false;
}

To avoid using the flag variable found, we can move the inner loop into a separate function, which instead of setting a flag variable + break, returns false immediately:

bool isSubstr(const std::string & s, size_t start, const std::string & pattern)
{
    for (auto i = 0; i < pattern.size(); i++)
    {
        if (s[start + i] != pattern[i])
        {
            return false;
        }
    }
    return true;
}

bool isSubstr(const std::string & word, const std::string & pattern)
{
    for (auto i = 0; i < word.size() - pattern.size() + 1; i++)
    { 
        if (isSubstr(word, i, pattern))
        {
            return true;
        }
    }
    return false;
}

Do not access array elements out of bound

As one of the answers mentioned, pattern[pattIdx] may be out of bounds in this code:

while (i < word.size() && pattern[pattIdx] == word[i])
{
    pattIdx++;
    i++;
} 

Although the code happens to work, this is a bad practice, therefore it's better to avoid. Which is easy enough to do, see the example I gave in the previous point.

Answer 4

Another way to Simplify the loop logic
(and explicitly avoid using oob indices):

    const size_t
        wordSize = word.size(),
        pattSz = pattern.size(),
        lastStart = wordSize - pattSz;
    // iterate possible pattern starts in word
    for (int wordIdx=0; wordIdx <= lastStart ; wordIdx++)
    {
        // iterate over pattern as long as each letter matches with word's
        for (int pattIdx = 0  /* , wi = wordIdx */// either two iteration variables...
             ; ; pattIdx++    /* , wi++ */)
        {
            if (pattIdx == pattSz)  // ... we have found a pattern
            {
                return true;
            }
            if (pattern[pattIdx] != word[wordIdx + pattIdx /* wi */])  // ... or add offset
            {
                break;
            }
        } 
    }
    return false;  // tried every index in vain

(main() in SGML comment)