算法---rfind

此前已经实现了find方法，文章地址：

算法---查找子串

今天将要实现的方法是rfind，find是从左侧开始查找，rfind是从右侧开始查找，以下面的字符串为例

cdeabcdeaba

如果是查找字符串cde，那么find方法返回的是0，而rfind方法返回的是5。

如果你已经掌握了find方法的精髓，其实写出一个rfind方法并不难，从思路上讲完全一样，但从右侧开始查找子串，逻辑上又有很多别扭的地方

首先，遍历字符串的过程要从右侧开始

其次，比较的字符不再是子串的首个字符，而是子串的末尾字符，找到末尾字符后还要比较剩余的部分

最后还要反向的计算子串开始的位置

这类算法题目并不复杂，需要的是一点点耐心和理性的分析

#coding=utf-8

string = "cdeabcdeaba"
def rfind(string,sub):
    index = -1
    for i in range(len(string)-1,-1,-1):
        if string[i] == sub[-1]:
            m = i
            n = len(sub)-1
            while n >= 0 and m >=0 and string[m] == sub[n]:
                m -= 1
                n -= 1

            if n == -1:
                return m + 1

    return index

print rfind(string,'cde')