Hi,
Any pointer at algorithm teaching for the substring and shifted index m ethod? I search online but ti doesn’t seem to be a usual terminology.
Ice Hunter and Northwest both use the substring search algorithm, but I found the code comments and the level explanations (help/hints) quite poor. The hint talks about double loop, it does not explain the algorithm.
My son and I can code at basic level, but I am not familiar with the algorithm these levels try to teach.
I try to understand the algorithm, not the code.
We get the code working, but not the “why” behind:
why do we “iterate through the start indexes only.”, what is the purpose of rightedge
why using “i in range(rightEdge + 1):” to parse the word/text, as opposed to start from the beginning?
Once in the nested loop, why using shiftedIndex, for what purpose, as opposed to start comparing from the substring’s beginning?
Hi Al and welcome to the forum hope you find it useful and your problem gets solved and please post your code so we can help you solve your problem!
-Zax
Hi Zax,
Sorry but I don’t have a problem with the code itself, rather the level (ice hunter/ northwest) comments and hints explaining the algorithm, explaining what is necessary, and more importantly why.
So the question is rather trying to understand the algorithm referred to by these levels: substring search by shifted index.
The Hints mention it’s a well known algorithm but it does not explain it, it only explains nested loop.
I am looking for more guided explanation of the algorithm itself.
The coding part of it has already been covered in past forum/Q&A discussion, fore example:
sorry I cannot paste all the links, new users cannot paste more than 2 links.
But I am not after coding help, rather algorithm explanation.
Hi Al-al,
I’m a learner as well - I’m about 3 paces ahead of you in the levels. Your questions are good!
I think:
For the first question, rightEdge is defined as the word length - substring length. If you started checking the first letter of the substring at the last letter of the word, then I suspect when it went on to check the second letter of the substring it would have nothing to compare it with, so it would send back an error. Putting the variable of rightEdge stops this happening.
For the third question, when you get to checking the letters, you want to uncorrect for the change you made with rightEdge, as you now want to check all the letters. You achieve this by adding i and j to make the new variable shiftedIndex.
I’m still thinking about your question 2. I’ll get back to you if I come up with an answer (or someone who knows more than me might be able to help ).
Say you have a 6 letter word abcdef. If you wanted to check for 1 letter, then you’d run the loop 6 times (starting on a, b, c, d, e, f).
If you wanted to check a 2 letter substring then you’d check the loop 5 times (starting on a, b, c, d, e). But 6 - 2 = 4 (not 5). Similarly if you wanted to check a 3 letter substring, you’d check the loop 4 times, but 6 - 3 = 3, not 4. By doing the deduction you take away an extra 1, so you have to add it back in.
That all makes sense in my head, but if it’s coming out as gibberwaffle then please say, and I’ll let someone else have a go at explaining!
I’m going to lean towards, jka’s thoughts on this. I’ve been busy with work, so am just now getting to this post, so not much time to ponder. What he says makes sense to me.
).
