目录
方法2
算法
示例
输出
首页 后端开发 C++ 检查给定句子中,子串S2的任何出现后是否出现子串S1

检查给定句子中,子串S2的任何出现后是否出现子串S1

Aug 26, 2023 am 11:13 AM
检查 给定句子 子串s 出现

检查给定句子中,子串S2的任何出现后是否出现子串S1

在这个问题中,我们需要检查子字符串S1是否出现在给定字符串S中子字符串S2的任何出现之后。我们可以比较S1和S2在字符串S中的起始索引来解决这个问题。 p>

问题陈述——我们给出了三个子字符串,名为 S、S1 和 S2。字符串 S 始终包含 S1 作为子字符串。我们需要检查给定字符串 S 中子字符串 S1 是否出现在子字符串 S2 出现之后。

示例

输入– S =“abxtutorialspointwelcomepoint”,S1 =“欢迎”,S2 =“点”;

输出 – 是

解释 – 在字符串 S 中,“point”子字符串出现了 2 次。一个在“欢迎”之前,另一个在“欢迎”之后。所以,我们可以说字符串 S1 出现在字符串 S2 的任何出现之后

输入–   S = "abcdefgh", S1 = "abcd", S2 = "gh";

输出 – 否

解释S1位于字符串S的开头。因此,S1不会出现在子字符串S2之后。

输入– S =“abce”,S1 =“bc”,S2 =“xy”;

输出 – 否

说明 – 由于字符串 S2 不存在于字符串 S 中,因此打印 No。

方法 1

在这种方法中,我们将找到 S2 子字符串的所有起始索引并将它们存储在集合中。之后,我们将得到S1的起始索引。我们将 S2 的每个起始索引与 S1 的起始索引进行比较,如果我们发现集合中的任何值小于 S2 的起始索引,则可以说子字符串 S1 出现在子字符串 S2 的任何出现之后。

算法

  • 定义存储子串S2起始索引的集合。

  • 使用 find() 方法查找 S2 子字符串的第一个起始索引。

  • 使用while循环获取子字符串S2的所有起始索引,并使用insert()方法将它们存储到集合中。

  • 遍历设定值。如果任何值小于给定字符串 S 中子字符串 S1 的起始索引,则返回 true。

  • 最后返回 false。

示例

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
bool isS1AfterS2(string& S, string& S1, string& S2) {
   // set to store indices of S2 in S
   unordered_set<int> indices;
   // Find all occurrences of S2 in S, and store them in set
   size_t found = S.find(S2);
   while (found != string::npos) {
      indices.insert(found);
      found = S.find(S2, found + 1);
   }
   // Compare starting indices of S1 with S2
   for (const int& index : indices) {
      if (index < S.find(S1)) {
          return true;  // S2 appears before S1
      }
   }
   return false;  // S1 appears before or at the same position as S2
}
int main(){
   string S = "abxtutorialspointwelcomepoint";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
          cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}
登录后复制

输出

Yes, string S1 appears after string S2.
登录后复制
登录后复制

时间复杂度 - O(N*K),因为我们需要找到字符串 S2 的起始索引。

空间复杂度 - O(N),因为我们存储字符串 S2 的起始索引。

方法2

在这种方法中,我们将遍历字符串。如果我们发现 S2 在 S1 出现之前出现,则返回 true,因为字符串 S 始终包含字符串 S1。

算法

  • 定义len、n1和n2变量来存储变量的长度。

  • 开始遍历字符串。

  • 定义‘temp 字符串,并使用从第 i 个索引开始的长度为 n2 的子字符串对其进行初始化。

  • 如果 temp == S2,则返回 true。

  • 从第 i 个索引开始取长度为 n1 的子字符串。如果 temp == s1,则返回 false。

  • 最后返回true。

示例

#include <bits/stdc++.h>
using namespace std;
bool isS1AfterS2(string &S, string &S1, string &S2){
   // store the length of the strings
   int n1 = S1.size(), n2 = S2.size();
   // Traverse the string S from left to right
   for (int i = 0; i <= S.size() - n2; i++){
      // temporary string to store substring
      string temp;
      // get the substring
      temp = S.substr(i, n2);
      // if we find the string S2, return true as s1 always present in s.
      if (temp == S2){
          return true;
      }
      temp = S.substr(i, n1);
      // If we find s1 before s2, return false
      if (temp == S1){
          return false;
      }
   }
   return true;
}
int main(){
   string S = "abxtutorialspointwelcome";
   string S1 = "welcome", S2 = "point";
   if(isS1AfterS2(S, S1, S2)) {
      cout << "Yes, string S1 appears after string S2.";
   } else { 
      cout << "No, string S1 does not appear after string S2.";
   }
   return 0;
}
登录后复制

输出

Yes, string S1 appears after string S2.
登录后复制
登录后复制

时间复杂度 – O(N*min(n1, n2)),因为我们找到长度为 n1 和 n2 的子字符串。

空间复杂度 - O(min(n1, n2),因为我们存储子字符串。

在第一种方法中,我们使用集合来存储S2的起始索引,这比第二种方法的代码需要更多的空间。第二种方法的代码比第一种方法更具可读性。另外,程序员可以尝试解决检查子串S2是否出现在S1出现之后的问题。

以上是检查给定句子中,子串S2的任何出现后是否出现子串S1的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

如何在Python中检查应用程序是否打开? 如何在Python中检查应用程序是否打开? Aug 26, 2023 pm 06:49 PM

正在执行的程序称为进程。进程可以是当前操作系统上运行的应用程序,也可以是与操作系统相关的应用程序。如果一个应用程序与操作系统相关,它首先会创建一个进程来执行自己。其他应用程序依赖操作系统服务来执行。大多数应用程序是操作系统服务以及维护操作系统、软件和硬件的后台应用程序。在python中,我们有不同的方法来检查应用程序是否打开。让我们一一详细了解它们。使用psutil.process_iter()函数psutil是python中的一个模块,它为用户提供一个接口来检索正在运行的进程和系统利用率的信息

如何在Python中检查一个对象是否可迭代? 如何在Python中检查一个对象是否可迭代? Aug 25, 2023 pm 10:05 PM

可迭代对象是可以使用循环或可迭代函数迭代其所有元素的对象。列表、字符串、字典、元组等都称为可迭代对象。在Python语言中,有多种方法可以检查对象是否可迭代。让我们一一看看。使用循环在Python中,我们有两种循环技术,一种是使用“for”循环,另一种是使用“while”循环。使用这两个循环中的任何一个,我们可以检查给定的对象是否可迭代。示例在这个例子中,我们将尝试使用“for”循环迭代一个对象并检查它是否被迭代。以下是代码。l=["apple",22,"orang

拼写检查在团队中不起作用[修复] 拼写检查在团队中不起作用[修复] Mar 06, 2024 am 09:10 AM

我们已经开始注意到,有时拼写检查停止工作的团队。拼写检查是有效沟通的基本工具,任何对它的打击都会对工作流程造成相当大的破坏。在本文中,我们将探讨拼写检查可能无法按预期运行的常见原因,以及如何将其恢复到以前的状态。所以,如果拼写检查在团队中不起作用,请遵循本文中提到的解决方案。为什么Microsoft拼写检查不起作用?Microsoft拼写检查无法正常工作可能有多种原因。这些原因包括不兼容的语言设置、拼写检查功能被禁用、MSTeam或MSOffice安装损坏等。另外,过时的MSTeams和MSOf

Windows11中如何检查 SSD 运行状况?Win11上检查 SSD 运行状况的方法 Windows11中如何检查 SSD 运行状况?Win11上检查 SSD 运行状况的方法 Feb 14, 2024 pm 08:21 PM

Windows11中如何检查SSD运行状况?对于其快速的读取、写入和访问速度,SSD正在迅速取代HDD,但即使它们更可靠,您仍然需要在Windows11中检查SSD的运行状况。怎么去操作呢?本篇教程小编就来为大家分享一下方法吧。方法一:使用WMIC1、使用按键组合Win+R,键入wmic,然后按或单击“确定”。Enter2、现在,键入或粘贴以下命令以检查SSD运行状况:diskdrivegetstatus如果您收到“状态:正常”消息,则您的SSD驱动器运行正

Golang中如何检查字符串是否以特定字符开头? Golang中如何检查字符串是否以特定字符开头? Mar 12, 2024 pm 09:42 PM

Golang中如何检查字符串是否以特定字符开头?在使用Golang编程时,经常会遇到需要检查一个字符串是否以特定字符开头的情况。针对这一需求,我们可以使用Golang中的strings包提供的函数来实现。接下来将详细介绍如何使用Golang检查字符串是否以特定字符开头,并附上具体的代码示例。在Golang中,我们可以使用strings包中的HasPrefix

如何在Java中检查ArrayList是否包含某个元素? 如何在Java中检查ArrayList是否包含某个元素? Sep 03, 2023 pm 04:09 PM

您可以利用List接口的contains()方法来检查列表中是否存在对象。contains()方法booleancontains(Objecto)如果此列表包含指定的元素,则返回true。更正式地说,如果且仅当此列表包含至少一个元素e,使得(o==null?e==null:o.equals(e)),则返回true。参数c-要测试其在此列表中是否存在的元素。返回值如果此列表包含指定的元素,则返回true。抛出ClassCastException-如果指定元素的类型与此列表不兼容(可选)。NullP

win11改win10系统教程的详细介绍 win11改win10系统教程的详细介绍 Jul 08, 2023 pm 09:21 PM

微软6月24号正式公布了win11系统,可以看到用户界面、开始菜单等和Windows10X中发现的非常相似。有的朋友在使用预览版的时候发现用的不习惯,想要改win10系统开使用,那么我们要如何操作呢,下面我们就来看看win11改win10系统教程,一起来学习一下吧。1、第一步是从Windows11打开新设置。在这里,您需要转到图像中显示的系统设置。2、在系统设置下,选择“恢复”选项。在这里,您将能够看到“以前版本的窗口”选项。您还可以在它旁边看到一个“返回”按钮,单击此按钮。3、您可以指定要返回

在C语言中编写一个程序,用于检查给定的年份是否为闰年 在C语言中编写一个程序,用于检查给定的年份是否为闰年 Sep 20, 2023 pm 03:33 PM

闰年有366天,而普通年有365天,任务是通过程序检查给定的年份是否为闰年。判断的逻辑可以通过检查年份是否能被400或4整除来实现,但如果不能被这两个数整除,则为普通年。示例Input-:year=2000Output-:2000isaLeapYearInput-:year=101Output-:101isnotaLeapyear算法StartStep1-&gt;declarefunctionbooltocheckifyearifaleapyearornotboolcheck(intye

See all articles