# Number of Strings That Appear as Substrings in Word
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-strings-that-appear-as-substrings-in-word)
Canonical: https://scaleengineer.com/dsa/problems/number-of-strings-that-appear-as-substrings-in-word
**Data structures:** Array, String
---
## Problem
Given an array of strings `patterns` and a string `word`, return _the **number** of strings in_ `patterns` _that exist as a **substring** in_ `word`.

A **substring** is a contiguous sequence of characters within a string.

**Example 1:**

**Input:** patterns = ["a","abc","bc","d"], word = "abc"
**Output:** 3
**Explanation:**
- "a" appears as a substring in "abc".
- "abc" appears as a substring in "abc".
- "bc" appears as a substring in "abc".
- "d" does not appear as a substring in "abc".
3 of the strings in patterns appear as a substring in word.

**Example 2:**

**Input:** patterns = ["a","b","c"], word = "aaaaabbbbb"
**Output:** 2
**Explanation:**
- "a" appears as a substring in "aaaaabbbbb".
- "b" appears as a substring in "aaaaabbbbb".
- "c" does not appear as a substring in "aaaaabbbbb".
2 of the strings in patterns appear as a substring in word.

**Example 3:**

**Input:** patterns = ["a","a","a"], word = "ab"
**Output:** 3
**Explanation:** Each of the patterns appears as a substring in word "ab".

**Constraints:**

* `1 <= patterns.length <= 100`
* `1 <= patterns[i].length <= 100`
* `1 <= word.length <= 100`
* `patterns[i]` and `word` consist of lowercase English letters.

# Approaches
## Brute-Force Manual Substring Search
This approach involves manually implementing a substring search algorithm. We iterate through each pattern and then, for each pattern, we iterate through all possible starting positions in the `word` to see if a match can be found. This is the most fundamental way to solve the problem but also the least efficient.
**Time:** O(N * W * M), where `N` is the number of patterns, `W` is the length of `word`, and `M` is the maximum length of a pattern. For each of the `N` patterns, we scan through `W` possible starting positions in `word`, and for each position, we compare up to `M` characters. · **Space:** O(1), as we only use a few variables to keep track of the count and loop indices, not dependent on the input size.
**Pros:** Simple to understand the logic from first principles.; Doesn't rely on built-in library functions for the core substring search logic.
**Cons:** Inefficient due to the triple nested loop structure, leading to a high time complexity.; Re-implements functionality that is already available and highly optimized in standard libraries.; More verbose and error-prone than using built-in methods.
### Explanation
The core idea is to simulate the process of finding a substring without using any library helpers. We take each pattern from the input array and try to find it within the `word`. To do this, we slide the `pattern` over the `word` one character at a time. For each possible starting position in `word`, we compare the corresponding segment of `word` with the `pattern`. If all characters match, we've found a substring. We then increment our counter and move on to the next pattern to avoid overcounting for a single pattern that might appear multiple times. 

```java
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        for (String pattern : patterns) {
            if (isSubstring(word, pattern)) {
                count++;
            }
        }
        return count;
    }

    private boolean isSubstring(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return true;
        if (n < m) return false;

        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break;
                }
            }
            if (j == m) {
                return true; // Found the pattern
            }
        }
        return false; // Pattern not found
    }
}
```
### Algorithm
- Initialize a counter `count` to zero.
- Loop through each `pattern` string in the `patterns` array.
- For each `pattern`, start a nested loop to check for its presence in `word`.
- This inner check involves another loop that iterates from the first character of `word` up to the last possible starting point for `pattern` (i.e., `word.length() - pattern.length()`).
- At each starting position `i` in `word`, we compare the substring of `word` of length `pattern.length()` starting at `i` with the `pattern` character by character.
- If a full match is found for the current `pattern`, we increment `count` and break the inner loops to move to the next pattern in the `patterns` array.
- After checking all patterns, the final `count` is returned.

## Using Built-in `contains()` Method
This is the most straightforward and practical approach for this problem. We can leverage the built-in `String.contains()` method which is highly optimized for substring searching. This method abstracts away the complexity of the search algorithm, leading to clean and efficient code.
**Time:** O(N * W * M), where `N` is the number of patterns, `W` is the length of `word`, and `M` is the average length of a pattern. The `contains` method has a time complexity of roughly `O(W * M)` in the worst case. However, the underlying implementation is often much faster in practice than a manual brute-force search due to optimizations (like KMP or Boyer-Moore algorithms). · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** Extremely simple and concise code.; Leverages optimized, built-in library functions, making it very efficient in practice for the given constraints.; Highly readable and less prone to implementation errors.
**Cons:** The exact performance depends on the language's specific implementation of the `contains` method, though it's generally very good.
### Explanation
The algorithm is very simple. We initialize a counter variable to zero. We then iterate through the `patterns` array one by one. For each `pattern` string, we call `word.contains(pattern)`. This method returns `true` if `pattern` is a substring of `word`, and `false` otherwise. If the method returns `true`, we increment our counter. After the loop finishes, the counter will hold the total number of patterns that are substrings of `word`, and we return this value. This is the intended and most common solution for such a problem in a practical or contest setting.

```java
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        int count = 0;
        for (String pattern : patterns) {
            if (word.contains(pattern)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count = 0`.
- For each `string pattern` in the `patterns` array:
-   Check if `word.contains(pattern)` is true.
-   If it is, increment `count`.
- After iterating through all patterns, return `count`.

## Advanced Approach: Suffix Automaton / Suffix Tree
For problems involving many substring queries on a single text, a more advanced approach is to use a specialized data structure like a Suffix Tree or a Suffix Automaton. This involves a pre-processing step to build the structure for the `word`, after which each pattern query can be answered very quickly. This approach is asymptotically the most efficient.
**Time:** O(W + S), where `W` is the length of `word` and `S` is the sum of the lengths of all strings in `patterns`. Building the automaton takes `O(W)`. Each query takes `O(M_i)` where `M_i` is the length of the pattern, so the total query time is `O(S)`. · **Space:** O(W), as the Suffix Automaton or Suffix Tree requires space proportional to the length of the `word` to store its nodes and transitions.
**Pros:** Asymptotically the most efficient approach, especially when the `word` is very long and there are many patterns to check.; Excellent performance for substring search after the initial preprocessing cost.
**Cons:** Very complex to implement correctly from scratch.; The overhead of building the data structure might make it slower than the simpler `contains()` method for small inputs like those specified in the problem constraints.; It is considered overkill for this particular problem.
### Explanation
This method separates the problem into two phases: preprocessing and querying. First, we process the `word` by building a data structure that indexes all of its substrings. A Suffix Automaton is a perfect fit, as it can be built in `O(W)` time and can check for the existence of any substring of length `M` in `O(M)` time. After the automaton for `word` is built, we simply iterate through each `pattern`, check for its presence in the automaton, and increment a counter if it's found. While this is the fastest approach in terms of time complexity, its implementation complexity is very high and not practical for this problem's constraints.

```java
// Conceptual Code - Suffix Automaton implementation is non-trivial
// and not expected for this problem. The built-in `contains` method
// is the practical and sufficient solution.
class Solution {
    public int numOfStrings(String[] patterns, String word) {
        // In a real-world scenario with massive scale, one would:
        // 1. Pre-process 'word' into a Suffix Tree/Automaton.
        // SuffixAutomaton sa = new SuffixAutomaton(word);
        
        // 2. Query for each pattern.
        int count = 0;
        for (String pattern : patterns) {
            // if (sa.isSubstring(pattern)) { 
            //    count++;
            // }
            
            // Given the constraints, this is the best approach:
            if (word.contains(pattern)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- **Preprocessing:** Build a Suffix Automaton or Suffix Tree for `word`. This takes `O(W)` time.
- **Querying:** Initialize `count = 0`.
- For each `pattern` in `patterns`:
-   Check if `pattern` exists in the pre-built data structure by traversing it. This takes `O(M_i)` time, where `M_i` is the length of the current pattern.
-   If it exists, increment `count`.
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int numOfStrings(String[] patterns, String word) {
    int ans = 0;
    for (String p : patterns) {
      if (word.contains(p)) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numOfStrings(vector<string> &patterns, string word) {
    int ans = 0;
    for (auto &p : patterns) {
      ans += word.find(p) != string ::npos;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numOfStrings(
        self, patterns: List[str], word: str) -> int: return sum(p in word for p in patterns)

```