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