字符串的包含

字符串的包含问题描述:给定一个长字符串a和一个短字符串b。请问,如何最快地判断出短字符串b中的所有字符都在长字符串a中?请编写函数boolStringContain(string&a,string&b)实现此功能。为简单起见,假设输入的字符串只包含大写英文字母。下面举几个例子:(1

大家好,欢迎来到IT知识分享网。

问题描述: 给定一个长字符串a和一个短字符串b。请问,如何最快地判断出短字符串b中的所有字符都在长字符串a中?请编写函数bool StringContain(string &a, string &b)实现此功能。为简单起见,假设输入的字符串只包含大写英文字母。

下面举几个例子:

 

(1)如果字符串a是”ABCD”,字符串b是”BAD”,答案是true,因为字符串b中的字母都在字符串a中,或者说b是a的真子集。

(2)如果字符串a是”ABCD”,字符串b是”BCE”,答案是false,因为字符串b中的字母E不在字符串a中。

(3)如果字符串a是”ABCD”,字符串b是”AA”,答案是true,因为字符串b中的字母A包含在字符串a中。

解题思路:

1.最直接的办法,蛮力轮询。对于这种方法,如果长字符串a的长度为n,短字符串b的长度为m,那么此算法需要比较次数为O(n*m)。显然该方法时间开销很大。

2.排序后轮询,根据题目只包括大写的英文字母,对两个字符串分别进行排序需要操作:O(mlogm)+O(nlogn),之后进行线性扫描需要O(n+m)

参考代码:

#include <bits/stdc++.h>

using namespace std;

bool StringContain( string &a , string &b )
{
    sort( a.begin() , a.end() );
    sort( b.begin() , b.end() );
    int lena = a.length();
    int lenb = b.length();
    for(int pa = 0 , pb = 0 ; pb < lenb ; )
    {
        while((pa < lena) && (a[pa] < b[pb]))
        {
            ++pa;
        }
        if((pa >= lena) || (a[pa] > b[pb]))
        {
            return false;
        }
        ++pb;
    }
    return true;
}
int main()
{
    string a  = "ABCD";
    string b[3];
    b[0] = "BAD";
    b[1] = "BCE";
    b[2] = "AA";
    for(int i=0;i<3;i++)
    {
        if(StringContain(a,b[i]))
            cout<<a<<"  contains  "<<b[i]<<endl;
        else
            cout<<a<<"  don't contain  "<<b[i]<<endl;
    }
    return 0;
}

GCC运行结果:

字符串的包含

3.位运算法。

将长字符串a的所有字符都存放在一个散列表(hash table)中,然后轮询短字符串b,看b中的每一个字符是否都在散列表中,若果都在则返回true,否则返回false

可以用位运算(26位整数表示)给相应的长字符串a就算出一个相对应的”签名”,然后将字符串b的每一个字符都放在a中进行查找。

参考代码:

#include <bits/stdc++.h>

using namespace std;

bool StringContain( string &a , string &b )
{
    int hash = 0;
    int lena = a.length();
    int lenb = b.length();
    for( int i = 0 ; i < lena ; i++)
    {
        hash |= (1 << (a[i] - 'A'));
    }
    for(int i = 0; i < lenb ; i++)
    {
        if( ( hash & ( 1 << ( b[i] - 'A' ) ) ) == 0)
            return false;
    }
    return true;
}
int main()
{
    string a  = "ABCD";
    string b[3];
    b[0] = "BAD";
    b[1] = "BCE";
    b[2] = "AA";
    for(int i=0;i<3;i++)
    {
        if(StringContain(a,b[i]))
            cout<<a<<"  contains  "<<b[i]<<endl;
        else
            cout<<a<<"  don't contain  "<<b[i]<<endl;
    }
    return 0;
}

GCC运行结果:

字符串的包含

该算法的空间复杂度为O(1),时间复杂度为O(n+m)。

 

免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/30246.html

(0)

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

关注微信