Checks whether substring S1 occurs after any occurrence of substring S2 in the given sentence

In this problem, we need to check if substring S1 occurs after any occurrence of substring S2 in a given string S. We can solve this problem by comparing the starting index of S1 and S2 in the string S. p>

Problem Statement - We are given three substrings named S, S1 and S2. String S always contains S1 as a substring. We need to check whether substring S1 appears after substring S2 in a given string S.

Example

Enter – S = "abxtutorialspointwelcomepoint", S1 = "Welcome", S2 = "point";

Output – Yes

Explanation – In string S, the “point” substring appears 2 times. One before "welcome" and the other after "welcome". So, we can say that string S1 occurs after any occurrence of string S2

Input– S = "abcdefgh", S1 = "abcd", S2 = "gh";

Output – No

ExplanationS1 is located at the beginning of string S. Therefore, S1 will not appear after substring S2.

Input– S = “abce”, S1 = “bc”, S2 = “xy”;

Output – No

Explanation – Since string S2 does not exist in string S, print No.

method 1

In this approach, we will find all starting indices of S2 substrings and store them in a collection. After that, we will get the starting index of S1. We compare each starting index of S2 with the starting index of S1 and if we find any value in the set is less than the starting index of S2, then we can say that substring S1 occurs after any occurrence of substring S2 .

algorithm

• Define the collection that stores the starting index of substring S2.

• Use the find() method to find the first starting index of the S2 substring.

• Use a while loop to get all the starting indices of substring S2, and use the insert() method to store them into a collection.

• Traverse the setting values. Returns true if any value is less than the starting index of substring S1 in the given string S.

• Finally returns false.

Example

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isS1AfterS2(string& S, string& S1, string& S2) {
   // set to store indices of S2 in S
   unordered_set<int> indices;
   // Find all occurrences of S2 in S, and store them in set
   size_t found = S.find(S2);
   while (found != string::npos) {
      indices.insert(found);
      found = S.find(S2, found + 1);
   }
   // Compare starting indices of S1 with S2
   for (const int& index : indices) {
      if (index < S.find(S1)) {
          return true;  // S2 appears before S1
      }
   }
   return false;  // S1 appears before or at the same position as S2
}
int main(){
   string S = "abxtutorialspointwelcomepoint";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
          cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Output

Yes, string S1 appears after string S2.

Time complexity - O(N*K), because we need to find the starting index of string S2.

Space complexity - O(N), since we store the starting index of string S2.

Method 2

In this method, we will iterate over the string. Returns true if we find that S2 occurs before S1, because string S always contains string S1.

algorithm

• Define len, n1 and n2 variables to store the length of the variable.

• Start traversing the string.

• Define the 'temp string and initialize it with a substring of length n2 starting at the i-th index.

• If temp == S2, return true.

• Get a substring of length n1 starting from the i-th index. If temp == s1, returns false.

• Finally returns true.

Example

#include <bits/stdc++.h>
using namespace std;
bool isS1AfterS2(string &S, string &S1, string &S2){
   // store the length of the strings
   int n1 = S1.size(), n2 = S2.size();
   // Traverse the string S from left to right
   for (int i = 0; i <= S.size() - n2; i++){
      // temporary string to store substring
      string temp;
      // get the substring
      temp = S.substr(i, n2);
      // if we find the string S2, return true as s1 always present in s.
      if (temp == S2){
          return true;
      }
      temp = S.substr(i, n1);
      // If we find s1 before s2, return false
      if (temp == S1){
          return false;
      }
   }
   return true;
}
int main(){
   string S = "abxtutorialspointwelcome";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
      cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}

Output

Yes, string S1 appears after string S2.

Time complexity – O(N*min(n1, n2)), because we find substrings of length n1 and n2.

Space complexity - O(min(n1, n2), since we store substrings.

In the first method, we use a collection to store the starting index of S2, which requires more space than the code of the second method. The code of the second method is more readable than the first method. Alternatively, programmers can try to solve the problem of checking whether substring S2 appears after S1 appears.

The above is the detailed content of Checks whether substring S1 occurs after any occurrence of substring S2 in the given sentence. For more information, please follow other related articles on the PHP Chinese website!