# suffix array test code - Sasa Hasan <yonker@web.de> - 2008

import sys, sarray

def search_prefix(astring, sarray, suffix, findall=False):
    slen = len(suffix)
    left = 0
    right = len(astring)
    pivot = -1
    found = False
    # binary search for first matching suffix prefix
    while not found and left < right:
        pivot = (left+right)/2
        sp = sarray[pivot]
        if astring[sp:sp+slen] == suffix:
            found = True
        elif suffix < astring[sp:]:
            right = pivot
        else:
            left = pivot+1
    if found:
        if findall:
            # tries to extend all suffix prefix matches left and right
            # of the found pivot
            result = [ sarray[pivot] ]
            # find left matches
            if pivot > 0:
                leftp = pivot-1
                sp = sarray[leftp]
                while leftp >= 0 and astring[sp:sp+slen] == suffix:
                    result.append(sarray[leftp])
                    leftp -= 1
                    sp = sarray[leftp]
            # find right matches
            if pivot < len(astring)-1:
                rightp = pivot+1
                sp = sarray[rightp]
                while rightp+slen < len(astring) and astring[sp:sp+slen] == suffix:
                    result.append(sarray[rightp])
                    rightp += 1
                    sp = sarray[rightp]
            result.sort()
            return result
        return sarray[pivot]
    else:
        return -1

def main():
    text = sys.argv[1]
    sa = sarray.bsarray(text)
    suffixes = sys.argv[2:]
    print
    print "INPUT:", text
    for s in suffixes:
        print "SUFFIX:", s
        print "  using lfind: ", text.find(s)
        print "  using rfind: ", text.rfind(s)
        print "  using sarray (first match):", search_prefix(text, sa, s)
        print "  using sarray (all matches):", search_prefix(text, sa, s, True)
    print

if __name__ == "__main__":
    main()