字符串包含

http://www.nowcoder.com/questionTerminal/661e24c11de64e78804fdce653dafb0e

题目难度：一星
考察点：字符串

方法1：暴力

1. 分析：

这个题的意思就是给定两个字符串a和b，判断a是不是b的子串或者b是不是a的子串，我们先只考虑一种情况即a是不是b的子串，另外一种情况是一样的，那么对于这种情况来说，我们可以假设a的长度为lena,b的长度为lenb，那么我们可以枚举i从0到lenb-lena,然后j从0到lena，然后判断它们的每一位是不是相等即b[i+j]是不是等于a[j]，如果每一位都相等，那么显然a是b的子串，否则i继续遍历，知道遍历到lenb-lena之后都没有找到与a相等的子串，那么就判定a不是b的子串。

算法实现：
(1). 首先输入两个字符串。
(2). 根据上述算法写一个判断一个子串是不是另外一个字符串子串的函数。
(3). 将两个字符串分别作为子串传入上述的函数，输出结果。

2. 复杂度分析：

时间复杂度：O(n*(n-m))
空间复杂度：O(n+m)

3. 代码：

#include <bits/stdc++.h>
using namespace std;
bool judge(string s1, string s2) {
 int len1 = s1.size(), len2 = s2.size();
 if(len2 > len1) return false;
 for(int i=0; i<=len1-len2; i++) {
     int ok = 1;
     for(int j=0; j<len2; j++) {
         if(s1[i+j] != s2[j]) {
             ok = 0;
             break;
         }
     }
     if(ok) return true;
 }
 return false;
}
int main() {
 string s1, s2;
 while(cin>>s1>>s2) {
     if(judge(s1, s2) || judge(s2, s1)) cout<<1<<endl;
     else cout<<0<<endl;
 }
 return 0;
}

方法2：KMP

1. 分析：

上述的代码虽然能够通过本题，但是还是复杂度还是稍微有点高接下来介绍一种KMP的方法来判断是否为子串， KMP算法的核心思想：避免不必要的回溯，主串不进行回溯，子串在每个位置的回溯位与当前位置之前字符与自身开始几位的字符匹配程度来决定。由于KMP算法不能只言片语的介绍完毕，想要弄懂KMP算法，还是得去找一些相关的文档看一下，才能弄懂，这里只能简单介绍一下算法流程。

算法实现：
(1). 首先输入两个字符串。
(2). 写一个获取next数组的函数，next 数组考虑的是除当前字符外的最长相同前缀后缀。
(3). 根据KMP算法写一个判断a字符串是否为b字符串的子串函数。
(4). 将两个字符串分别作为子串传入上述的函数，输出结果。

2. 复杂度分析：

时间复杂度：O(n+m)
空间复杂度：O(n+m)

3. 代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
int nxt[MAXN];
void getnxt(string p) {
 nxt[0] = -1;
 nxt[1] = 0;
 int j = 1, k = 0, len = p.size();
 while (j + 1 < len) {
     if (k == -1 || p[k] == p[j]) nxt[++j] = ++k;
     else k = nxt[k];
 }
}
bool judge(string s, string p) {
 getnxt(p);
 int i = 0, j = 0, lens = s.size(), lenp = p.size();
 while(i<lens && j<lenp){
     if(s[i]==p[j] || j==-1){
         i++;
         j++;
     }
     else j = nxt[j];
 }
 if(j == lenp) return 1;
 return 0;
}
int main() {
 string s1, s2;
 while(cin>>s1>>s2) {
     if(judge(s1, s2) || judge(s2, s1)) cout<<1<<endl;
     else cout<<0<<endl;
 }
 return 0;
}