字符串的包含

给定一长字符串a和一短字符串b,请问如何最快地判断出短字符串b中的所有字符是否都在字符串a中。 解法一：蛮力轮询：时间复杂度O(M*N); 解法2：排序轮询：时间复杂度O（mlongm)+O(nlongn）+O（m+n）； 解法3：素数相乘：时间复杂度为O(M+N),乘积可能过大 解法4：位运算 c++代码如下：

点击(此处)折叠或打开

#include<iostream> //#include<alogrithm> using namespace std; bool isContained(string &a,string &b) {     int hash = 0;//初值重要     for (int i = 0;i < a.length();i++)     {         hash |= (1 << (a[i]-'A'));     }     for (int j = 0;j < b.length();j++)     {         if ((hash & (1 << b[j]-'A')) == 0)             return false;     }     return true; } int main() {     string s1("ASD");     string s2("AF");     cout << isContained(s1,s2)<< endl;     return 0;      } 时间复杂度O(M+N)。 传说还有更简单的算法，望大神指教 <script>window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdMiniList":false,"bdPic":"","bdStyle":"0","bdSize":"16"},"share":{}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];</script> 阅读(132) | 评论(0) | 转发(0) | 0

上一篇：list_for_each_entry

下一篇：字符串的排列组合

相关热门文章 test123编写安全代码——小心有符号数...使用openssl api进行加密解密...一段自己打印自己的c程序...彻底搞定C语言指针详解-完整版... 给主人留下些什么吧！~~ 评论热议