设计一个算法，在串 str 中查找字符串 substr 最后一次出现的位置（不能使用 stl）。

### 回答1：
该算法可以通过遍历字符串，记录最后一次出现子串的位置来实现。具体实现可以使用双指针，一个指向字符串，一个指向子串，在遍历字符串的过程中，如果当前字符与子串匹配，则将子串指针后移，同时记录当前位置为最后一次出现子串的位置。最终返回最后一次出现子串的位置即可。

### 回答2：
首先我们需要了解一下什么是字符串的最后一次出现位置：指的是在主字符串中子字符串出现的最后一次位置。比如说：主字符串为abaababa、子字符串为ab，那么ab出现的最后一次位置为5。

可以使用双指针来实现查找子串在主串中最后一次出现位置的算法。具体步骤如下：

1.首先我们需要遍历主串的每一个字符，当找到一个与子串的第一个字符相同的字符时，我们从该位置开始与子串进行比较。

2.为了从后往前查找子串最后一次出现位置，我们需要从后往前进行比较。

3.如果找到了子串，就将此时的位置记录下来。然后继续向后遍历主串，重新开始比较。

4.当主串遍历完后，最后一次出现的位置也就被记录下来了。

代码实现如下：

int lastIndexOfSubstr(string str, string substr) {
    int mainlen = str.length();
    int sublen = substr.length();
    int i,j,k;
    for( i=mainlen-sublen; i>=0; i-- ) { //从后往前遍历主字符串
        for(j=0,k=i; str[k]==substr[j] && j<sublen; j++,k++ );//从后往前比较
        if( j==sublen ) {//找到子字符串
            return i;//返回位置
        }
    }
    return -1;//未找到
}

时间复杂度为O(n*m)，n为主串长度，m为子串长度。因为需要遍历每一个字符，并且从后往前比较每一个字符，所以时间复杂度比较高，不适合大规模的数据处理。

### 回答3：
为了在字符串中查找子串的最后一次出现位置，我们可以使用“反向查找”的方式来解决。也就是从字符串的末尾开始，逐个比较子串与字符串中的字符，找到最后一次出现子串的位置。

具体来说，我们可以使用两个指针：一个指向字符串的末尾，另一个指向子串的末尾。然后，逐个比较两个指针指向的字符是否相等，如果相等，则将两个指针都往前移动一位；如果不相等，则将字符串中的指针往前移动一位，并将子串指针指向子串的末尾，重新开始比较。

当子串指针指向子串的开头时，表示找到了子串在字符串中的最后一次出现位置，即字符串指针所指向的位置。如果在遍历完整个字符串后，子串指针仍指向子串的一部分，则说明子串在字符串中不存在。

下面是使用 C++ 实现该算法的代码示例：

int lastIndexOf(const string& str, const string& substr) {
    int strLen = str.length();
    int substrLen = substr.length();

    if (substrLen == 0) {
        return strLen;
    }

    int i = strLen - 1;
    int j = substrLen - 1;

    while (i >= 0 && j >= 0) {
        if (str[i] == substr[j]) {
            i--;
            j--;
        } else {
            i = i - substrLen + j;
            j = substrLen - 1;
        }
    }

    if (j < 0) {
        return i + 1;
    } else {
        return -1;
    }
}

该算法的时间复杂度为 O(m+n)，其中 m 和 n 分别为字符串和子串的长度。因为算法只需遍历字符串一次，因此空间复杂度为 O(1)。