题目描述

扩展题目一------排序次数

输入两个字符串 s 和 t，判断 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

输入描述

每个输入包含一个测试用例。每个测试用例包含两行长度不超过 10 的不包含空格的可见 ASCII 字符串。

输出描述

输出一行 “Yes” 或者 “No” 表示结果。

示例

输入

x.nowcoder.com
ooo

输出

Yes

参考解法：

// 判断是否是子序列
// 子序列不要求在原字符串中是连续的

import java.util.Scanner;
public class Demo_05 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char s1[] = sc.next().toCharArray();
        char s2[] = sc.next().toCharArray();
        int i=0,j=0;
        while (i<s1.length && j<s2.length){
        // 关键在于把短字符串中的每一个字符都与长字符串相比较
        // 相等就长度+1
        // 最后看长度是否与短字符串相等
            if(s1[i]==s2[j]){
                i++;
                j++;
            }else
                i++;
        }
        if(j==s2.length)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

定义

假如字符串 s 是 t 的子序列，那么可以删除 t 中的一些字符（也可以不删除），使得剩下的字符按原来的顺序排列得到的字符串等于s。

例题

LeetCode 392
代码比较简单，故不加赘述，记录本帖的意义在于防止日后脑子瓦特想不出来。

时间复杂度：O(N + M)，N和M为两个字符串的长度。

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <map>
#include <set>
#include <cstring>
#include <climits>
#include <algorithm>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
using namespace std;

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int len_s = s.size();
        int len_t = t.size();
        int idx = 0;
        for (char ch : t) {
            if (ch == s[idx]) {
                ++idx;
                if (idx >= len_s)
                    break;
            }
        }
        return idx >= len_s;
    }
};

判断子字符串是否包含在原字符串中（且返回子字符串在原字符串中出现的位置）

一、说明

       此篇博文算是针对于是否包含字符串的加强版。
       判断子字符串是否实包含原字符串中可以参考：此篇博文

二、分析

 测试比较字符串位置
     
   说明：
      i:当前原字符串指针的位置
      j:当前比较字符串指针的位置
      weizhi：比较字符串第n次出现在原字符串的位置
      一个中文字符占两个字节
       
      第一种：
      原字符串：贾房贾测贾
      比较字符串：贾

   原字符串                     比较字符串                   比较字符串第n次出现在原字符串的位置
   i=2                             j=2                                weizhi=2
   i=6                             j=2                                weizhi=6
   i=10                            j=2                                weizhi=10
      第二种：
      原字符串：贾继康房贾继康测贾继康
      比较字符串：贾继康
    
   原字符串                     比较字符串                   比较字符串第n次出现在原字符串的位置
      i=6                             j=6                                weizhi=2 
      i=14                            j=6                                weizhi=10 
      i=22                            j=6                                weizhi=18

      第三种：
      原字符串：测试贾继康房贾继康测贾继康侧设计费
      比较字符串：贾继
    
   原字符串                     比较字符串                   比较字符串第n次出现在原字符串的位置
      i=8                          j=4                                weizhi=6 
      i=16                         j=4                                weizhi=14 
      i=24                         j=4                                weizhi=22

三、代码

/* 
     程序功能：
            1:判断子字符串是否实现在原字符串中
            2:且返回出现在原字符串所在的位置


 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//int is_in(char s, char c);
int is_in(char *s, char *c, int location[]);
int main()
{
    char str[100] = "测试贾继康房贾继康测贾继康侧设计费";
    char str1[100] = "贾继康";

    //int *location = (int *)malloc(n * sizeof(int));
    int loc[250] = {0};
    int *location = loc;

    if (is_in(str, str1, location) == 1)
    {
        printf("原文件包含比较字符串\n");
        for (int i = 0; i < sizeof(location); i++)
        {
            if (location[i] != 0) //待查字符串在原字符串中不为空
            {
                printf("所在的位置：%d\n", location[i]);
            }
        }
    }
    else
    {
        printf("原文件不包含指定字符串\n");
    }
}

// 子函数
int is_in(char *s, char *c, int location[])
{
    int i = 0, j = 0, flag = -1;
    int firstW = 0;
    int num = 0;
    while (i < strlen(s) && j < strlen(c)) // s：原字符串，c: 比较字符串
    {
        if (s[i] == c[j]) // 指针所指位置的字符
        {                 //如果字符相同则两个字符都增加
            i++;
            j++;
        }
        else
        {
            i = i - j + 1; //主串字符回到比较 最开始比较的 后一个字符
            j = 0;         //字串字符重新开始
        }

        if (j == strlen(c)) //如果匹配成功
        {
            flag = 1; //字串出现
            //i-strlen(c) 比较字符在原字符串中第一次出现的位置
            printf("此时原字符串指针i的位置 %d\n", i);
            printf("此时比较字符串指针j的位置 %d\n", j);
            printf("比较字符串在原字符串中第一次出现的位置 %d\n\n", i - strlen(c) + 2); // i-strlen(c)+2
            location[num] = i - strlen(c) + 2;
            num++;
            j = 0;
            continue;
            /* if (s[i] == '\0' || s[i] == '\n')
            {
                printf("结束\n");
                break;
            } */
            //return i-strlen(c)+2;
            //break; // 第一次出现了不能结束
        }
    }

    return flag;
    //return i-strlen(c) +2;
}

四、结果

五、补充

      目的：int型数字转换为char型字符串
      分析：
            1、将所有的int型数字通过拼接，形成int型数组
            2、再将int型数组转化为char型字符串