文档章节

字符串的包含

htq
 htq
发布于 2016/07/26 09:41
字数 366
阅读 3
收藏 0

要求:给定一个主串X和子串Y判断主串是否包含子串,包含是指子串中的所用字符均在主串中出现,所谓出现不要求连续,如:主串X:abcdef  子串为:Y:cde,Z:ade,M:adx,则答案为true,true false,要求空间复杂度为O(1)

注意字符串的包含与字符串的查找的不同,具体可以参考我的博客: 字符串的查找

思路:因为是字符串的处理且要求空间复杂度为O(1),所以自然想到用哈希表处理,先扫描长串,然后用hash对长串中出现的字符进行标记,标记为1,接着在短串种扫描看对应的hash表中值是否为1,若存在一个不为1,则输出false,否则,输出ture。

基于此思路代码如下:
#include<iostream>
using namespace std;
void main()
{
    string X="ABCDEF";
	string Y="CDE";
	int hash[26]={0};
	for(int i=0;i<X.length();i++)
	{
		if(hash[X[i]-'A']==0)
			hash[X[i]-'A']=1;
	}
	for(int i=0;i<Y.length();i++)
	{
		if(hash[Y[i]-'A']==0)
		{
			cout<<"false"<<endl;
			return ;
		}
	}
	cout<<"true"<<endl;
}
程序运行结果如下:
<img src="http://img.blog.csdn.net/20160310162019518" alt="" />

推广:从这道题可以推广为,在一个字符串中查找第一个只出现一次的字符。只需将hash表中的值进行累加操作即可,hash表中第一个值为1的即为第一次出现一次的字符。



本文转载自:http://blog.csdn.net/htq__/article/details/50847668

共有 人打赏支持
htq

htq

粉丝 19
博文 67
码字总数 1007
作品 3
武汉
PHP 正则——一些常用的特殊字符。

p+ 匹配任何一个至少包含p的字符串 p* 匹配任何包含零个或多个p的字符串 p? 匹配任何包含零个或一个P的字符串 可选(类似) p{2} 匹配任何包含两个P序列的字符串 p{2,3} 匹配任何包含两个或三个...

virhuiai
2013/03/25
0
0
Swift3.0语言教程查找字符集和子字符串

Swift3.0语言教程查找字符集和子字符串 Swift3.0语言教程查找字符集和子字符串,在字符串中当字符内容很多时,我们就需要使用到查找字符集或者子字符串的方法。以下我们将讲解3种查找字符集和...

大学霸
2016/11/11
63
1
如何在 Linux shell 中找出所有包含指定文本的文件

目标:本文提供一些关于如何搜索出指定目录或整个文件系统中那些包含指定单词或字符串的文件。 难度:容易 约定: - 需要使用 root 权限来执行指定命令,可以直接使用 root 用户来执行也可以...

作者: Lubos Rendek
2017/12/18
0
0
python3-快速输出所有字母、数字等

  0x00 使用chr转换ASCII码   1、输出所有的大写字母   print([chr(i) for i in range(65,91)])   2、输出所有小写字母   print([chr(i) for i in range(97,123)])   3、输出所有...

linux运维菜
07/09
0
0
字符串的小方法

本博文包含upper()、lower()、isupper()、islower()、isX、startswith()、endswith()、join()、split()、 upper(),lower():将字符串中所有字母转化为大写和小写,其他字符不变。isupper(),i...

v_fanyunxiao
2017/08/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

React 服务器渲染原理解析与实践

网盘下载地址 React 服务器渲染原理解析与实践 本套课程,讲解了React中SSR技术的整个搭建思路及流程,完整的从原理上讲清楚了SSR的概念,重点在于讲解编写SSR框架遇到的各种知识点,以及细节...

qq__2304636824
46分钟前
1
0
Jenkins使用

clean install -Dmaven.test.skip=true

1713716445
56分钟前
0
0
多线程

1. 多线程概念。并发和并行的概念。 多线程指的是一段时间内cpu同时执行多个线程。一个程序至少运行>=1个进程,进程就是运行中的程序,而一个进程至少运行>=1个线程,线程是操作系统能调度的...

鱼想吃肉
今天
2
0
HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
今天
3
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部