Substring C++ Example
Problem
You have the following function signature int Contains(char* s1, char* s2, int n1, int n2) where s1, s2 are two strings and n1, n2 are their respective lengths. The function should return 1 if the s1 contains s2 otherwise it returns 0. For example if s1 = abcdefg and s2 = acg then it should return 1 because all the characters in acg are found in s1 with the same order regardless of their position in s1. In other words the characters must be in s1 but not necessarily adjacent. Here is another example s1= abcdefg and s2 = acb, in this case the function should return false although all characters can be found in s1 but they do not maintain the sequence.
Solution
You need to loop in the second string and for each character you try to find a match in the first string. If you can not find a match any time then return false. Otherwise save the position of the match in the first string so that you start after it in the next iteration in order to keep track of the order. Once the two nested loops are finished without returning false then you can return true which means the second string is contained in the first string.
Code
Here is the code in C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
//Includes #include <iostream> //STD using namespace std; //Receives two strings and their sizes int Contains(char* s1, char* s2, int n1, int n2) { //Stores the position of the match //in the first string int save = -1; //Indicates a match was found int found = 0; //Loop in the second string for (int i = 0; i < n2; i++) { //Reset found for each inner loop iteration found = 0; //Start the loop right after the match //position in order to keep track of order for (int j = save + 1; j < n1; j++) { //Match was found if (s2[i] == s1[j]) { //Save its position //Indicate match was found //break the loop no need to //continue searching save = j; found = 1; break; } } //No match was found if (found == 0) return 0; } //All characters in the second //string were examined so we return //true otherwise it would have //returned above return 1; } //Main function void main() { //Sample strings char str1[] = "abcdefg"; char str2[] = "ag"; //Check string if (Contains(str1, str2, 7, 2)) { cout << "True" << endl; } else { cout << "False" << endl; } } |
About Author
Mohammed Abualrob
Software Engineer @ Cisco