int pattern-matching(text, pattern): if text == null || pattern == null: throw // assume pattern of 0 length is ok index = -1 for i = 0, i <= text.length - pattern.length, i++: for j = 0, j < pattern.length, j++: if text[i+j] != pattern[j]: break if j == pattern.length: index = i break return index
Update: pattern has char * which matches 0+ chars in text OR + which matches 1+ chars in text OR char ? which matches 1 char in text.
// example text: abcde pattern: b* pattern: b**** pattern: b+ pattern: b?
int pattern-matching(text, pattern): if text == null || pattern == null: throw for i = 0, i < text.length, i++: if text[i] == '*' || '+' || '?': throw "invalid char" index = -1 for i = 0, i < text.length, i++: k = i for j = 0, j < pattern.length: if pattern[j] == '*': while j < pattern.length && pattern[j] == '*': j++ if j == pattern.length: break while k < text.length && text[k] != pattern[j]: k++ if k == text.length: break else if pattern[j] == '+': while j < pattern.length && k < text.length && pattern[j] == '+': k++, j++ if j == pattern.length: break while k < text.length && text[k] != pattern[j]: k++ if k == text.length: break else if pattern[j] == '?': // do nothing else if text[k] != pattern[j]: break k++, j++ if j == pattern.length: index = i break return index[Hat tip to G]
No comments:
Post a Comment