When a mismatch occurs in the KMP algorithm at text position i and pattern position j,...

 

Transcribed Image Text:

When a mismatch occurs in the KMP algorithm at text position i and pattern position j, neither the mismatched text character T[i] nor pattern character P[j] are considered when shifting the pattern. In this question, you will modify KMP to make use of P[j] and T[i] when shifting the pattern. You must not alter the fundamental principles of the KMP algorithm; i.e. when the pattern is shifted, the prefix of the pattern that matches with the text T[k] for ki must not be rechecked. a) Describe how to modify the KMP failure array and/or algorithm to make use of P[j]. State and briefly explain the runtime of the modified pre-processing step and algorithm if they are different from KMP. b) Describe how to modify the KMP failure array and/or algorithm to make use of T[i]. State and briefly explain the runtime of the modified pre-processing step and algorithm if they are different from KMP. Consider the following two cases separately. i) T[i] is not a character that occurs in the pattern. ii) T[i] is a character that occurs in the pattern; i.e. when the pattern is shifted, the prefix of the pattern that matches the text T[k] for k i must not be rechecked.ad When a mismatch occurs in the KMP algorithm at text position i and pattern position j, neither the mismatched text character T[i] nor pattern character P[j] are considered when shifting the pattern. In this question, you will modify KMP to make use of P[j] and T[i] when shifting the pattern. You must not alter the fundamental principles of the KMP algorithm; i.e. when the pattern is shifted, the prefix of the pattern that matches with the text T[k] for ki must not be rechecked. a) Describe how to modify the KMP failure array and/or algorithm to make use of P[j]. State and briefly explain the runtime of the modified pre-processing step and algorithm if they are different from KMP. b) Describe how to modify the KMP failure array and/or algorithm to make use of T[i]. State and briefly explain the runtime of the modified pre-processing step and algorithm if they are different from KMP. Consider the following two cases separately. i) T[i] is not a character that occurs in the pattern. ii) T[i] is a character that occurs in the pattern; i.e. when the pattern is shifted, the prefix of the pattern that matches the text T[k] for k i must not be rechecked.ad