首页
学习
活动
专区
圈层
工具
发布
社区首页 >专栏 >算法学习之字符串包含

算法学习之字符串包含

作者头像
用户4415180
发布2022-06-23 14:07:05
发布2022-06-23 14:07:05
6460
举报
文章被收录于专栏:高并发高并发

问题描述:如果字符串B中的字母都能在A中出现,则字符串A包含字符串B,

本题可用位运算,用两个long long类型的数字参与位运算,两个long long类型正好128位,可以把字符串全部表示完,时间复杂度O(N),空间复杂度O(1);

代码语言:javascript
复制
#include <stdio.h>
#include <stdlib.h>
#define  MAX   50
int is_contain(const char *str1,const char *str2)
{
    long long tmp1 = 0,tmp2 = 0;//前64位放进tmp1,后64位放进tmp2;
    int i = 0,n;
    while(str1[i])
    {
        n = str1[i++] - '\0';
        if(n < 63)
            tmp1 |= 1<<n;
        else
            tmp2 |= 1<<(n%64);
    }
    i = 0;
    while(str2[i])
    {
         n = str2[i++] - '\0';
        if(n < 63)
        {
            if(!((1<<n)&tmp1))
                return 0;
        }
        else
        {
            if(!((1<<(n%64)&tmp2)))
                return 0;
        }
    }
    return 1;
}
int main()
{
    char str1[MAX],str2[MAX];
    scanf("%s %s",str1,str2);
    if(is_contain(str1,str2))
        printf("str1 contain str2\n");
    else
        printf("str1 does't contain str2");
    return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2016-02-21,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档