Given two strings, text and pattern, the task is to check whether pattern is present inside text.
The string text is the main string where we search.
The string pattern is the smaller string that we want to find.
A substring means a continuous part of a string.
Example 1
Input: text = takeuforward, pattern = forward
Output: true
Explanation: The pattern "forward" is present in the text "takeuforward", so the output is true.
Example 2
Input: text = datastructure, pattern = algo
Output: false
Explanation: The pattern "algo" is not present in the text "datastructure", so the output is false.
Approach: Simple String Matching
A simple way to check whether a pattern exists inside a string is to try matching it from every possible starting position.
Think of searching for the word "love" in the sentence "I love coding".
We do not randomly compare letters. Instead, we start from one position in the sentence and check whether the entire word matches character by character.
If the match fails, we move to the next position and try again.
String substring searching works in exactly the same way.
For each possible starting index in the main string, we compare the characters of the pattern with the corresponding characters of the text.
If all characters match, the pattern is present in the string.
If no starting position produces a complete match, then the pattern does not exist.
This approach is correct because every substring must begin at some index of the main string.
So, checking all possible starting positions guarantees that no valid occurrence is missed.
Algorithm
If the pattern is empty, return
truebecause an empty string is considered present inside any string.If the pattern length is greater than the text length, return
falsebecause a larger string cannot fit inside a smaller string.Start checking from the first possible index of
textbecause the pattern may begin from the start.For each starting index, compare characters of
patternwith characters oftextone by one because the full pattern must match continuously.If any character does not match, stop checking from that position because this starting point cannot contain the pattern.
If all characters of
patternmatch from any starting position, returntruebecause the substring is found.Move to the next starting index if the current position does not give a full match because the pattern may start later.
If all possible starting positions are checked and no full match is found, return
falsebecause the pattern is not present inside the text.
Dry Run
Check if String Contains a Given Substring
Solution
// Header#include <bits/stdc++.h>using namespace std;// Solution Classclass Solution {public: // Function to check whether pattern exists inside text bool containsSubstring(string text, string pattern) { // Empty pattern is always present in any string if (pattern.length() == 0) { return true; } // Pattern longer than text can never be a substring if (pattern.length() > text.length()) { return false; } // Try every possible starting index in text for (int i = 0; i <= text.length() - pattern.length(); i++) { // Assume current starting index gives a match bool matched = true; // Compare pattern with text from current starting index for (int j = 0; j < pattern.length(); j++) { // A single mismatch breaks current attempt if (text[i + j] != pattern[j]) { matched = false; break; } } // Full pattern matched from current starting index if (matched) { return true; } } // No valid starting index produced a complete match return false; }};// Driver Codeint main() { string text = "abcde"; string pattern = "cd"; Solution obj; cout << (obj.containsSubstring(text, pattern) ? "true" : "false"); return 0;}Time Complexity:
The algorithm checks every possible starting position of the pattern within the text. For each starting position, it may compare up to M characters of the pattern with the corresponding characters in the text. In the worst case, this comparison is performed for all N positions in the text. Therefore, the overall time complexity is O(N × M), where N is the length of the text and M is the length of the pattern.Space Complexity:
The algorithm only uses a constant amount of extra memory, such as loop indices and a variable to track whether the pattern matches. No additional arrays, strings, or data structures proportional to the input size are created. Therefore, the space complexity is O(1).
FAQs about Check if String Contains a Given Substring
1. What is a substring?
A substring is a continuous part of a string.
2. Does order matter in substring checking?
Yes. The pattern must appear in the same order inside the text.
3. Can frequency counting solve this problem?
No. Frequency counting only checks character counts. Substring search also needs correct order and continuous matching.
4. What happens if the pattern is empty?
An empty pattern is usually considered present inside any string.
5. What if the pattern is longer than the text?
Then the answer is false because a longer pattern cannot fit inside a shorter text.
Be the first to add a comment.