Saturday, August 01, 2015

string pattern matching

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