Transform strstr() in C to support wraparound mode
If you already know about the C library function strstr(), you would know that it accepts a string and a substring and returns the first occurrence of the substring within the string in its original state.
But what does “wraparound mode” mean?
What if the string is in a modified state? The generic NULL terminated byte string has a beginning and an endpoint(the endpoint being the NULL byte). What if the string never had any beginning or an end? What if both ends of a string were connected? The generic strstr() function will not work when such a string is given. I have decided to change this silly constraint.
Pointers, again?
To put it simply, yes I will be using pointers, not to make me look cool but to make it so very efficient and finish the job just as easily as other methods. So, I will be borrowing my custom strstr() code discussed in my earlier blog which also discusses in detail why I use pointers. This is yet another pointer-heavy code but bear with me here, it will all seem easy when you “wrap” your head around the concept (pun intended).
Then let us begin…
Here is the algorithm for my code:
Algorithm:
Step 1. Start
Step 2. Accept a string and a sub-string from the user
Step 3. If the character from the string is equal to the character in the sub-string, move on to the next character in each case and if the string is at its end, then reset the string to the beginning and raise a flag indicating a wraparound of the string
Step 4. If the characters don’t match, reset the sub-string to the beginning and move onto the next character in string
Step 5. Repeat steps 4 and 5 until one of the 2 conditions are satisfied:
a) The flag has been passed and the sub-string still has no matching characters
b) The string or the sub string are at their end points.
Step 6. If the sub-string is at the end, return the difference of the memory locations of the sub-string in string and the start point of the string
Step 7. Else return -1
Step 8. End
You may have a question about the algorithm and all for good reason:
The really suspicious steps 3 and 5 b)
OK it may look like both the steps will result in an infinite loop but it is, in fact, the opposite. It is done to prevent an infinite loop. When the string reaches the end, it gets wrapped around but only when there is a preceding character match between the string and the substring. The flag is only checked when there is no previous match.
Let there be code!
and the corresponding flowchart to go with it:
Lastly, I would like to thank my mentors at KGISL Institute of Technology for for giving me this opportunity and for being ready to guide me in the right direction to better myself as programmer and readying me to be able to solve problems such as these, and I would like to express my gratitude to everyone who has appreciated my previous blog.
If you think any changes belong here, feel free to contact me at tkksctwo@gmail.com
