题目描述

给定字符串 target和 source, 判断 target 是否为 source 的子序列。
你可以认为 target 和 source 中仅包含英文小写字母。
字符串 source可能会很长（长度 ~= 500,000），而 target 是个短字符串（长度 <=100）。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
（例如，“abc"是"aebycd"的一个子序列， 而"ayb"不是）。
请找出最后一个子序列的起始位置。

输入描述:

第一行为target，短字符串（长度 <=100）
第二行为source，长字符串（长度 ~= 500,000）

输出描述:

最后一个子序列的起始位置， 即最后一个子序列首字母的下标

示例1

输入
abc
abcaybec
输出
3

说明
这里有两个abc的子序列满足，取下标较大的，故返回3
备注:
若在source中找不到target，则输出-1

测试用例

abc
cabdef
-1

abc
afegbdefsec
0

abc
dfsabcdefahibjkic
9

C语言题解：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAX_SOURCE 600000
#define MAX_TARGET 110
int main()
{
    char target[105] = {0};
    char source[MAX_SOURCE] = {0};
    scanf("%s", target);
    scanf("%s", source);
    const int t_len = strlen(target);
    const int s_len = strlen(source);
    int i = t_len - 1;
    int j = s_len - 1;
    int idx = 0;
    while (i>=0 && j>=0) { // 从尾部到头部开始比较
        if (target[i] == source[j]) {
            if (i == 0) { // 当到达 target 头部时，找到位置，返回索引
                printf("%d", j);
                return 0;
            }
            i--;
        }
        j--;
    }
    printf("-1");
    return 0;
}

时间复杂度：O(n)