思路:
首先可以想到一个暴力的做法就是拿子串与模式串一一匹配,时间复杂度O(n^2)(讲道理这个应该是过不了的,但是我居然过了。。)
然后就是考虑一下怎么优化,(看的题解,感觉挺奇妙的)就题目不是说字符串只可能是小写字母[a,z],那么我们可以构造一个next[i][j]:表示模式串第i个字符到字符j的下标,有了一个东西如果我们进行匹配的话就可以省去多余的没用的匹配,比如abcdef,子串ac,我们匹配完a,直接next[a][c] = 3,这样就直接去和第三个字符匹配,那么next数组怎么构造呢,还需要一个last[i]:表示字符i距离前面字符的最近位置,这样从后往前面扫就可以构造next数组了。然后这题就出来了。
O(n^2)代码:
#include<bits/stdc++.h> using namespace std; void solved(){ string mo;cin>>mo; int n;cin>>n; vector<string>ve; for(int i = 1; i <= n; i++){ string a;cin>>a; ve.push_back(a); } //noiauwfaurainairtqltqlmomomo //1 //ooooo for(int i = 0; i < ve.size(); i++){ string s = ve[i]; int cnt = 0; int r = 0; for(int i = 0; i < s.size(); i++){ while(s[i] != mo[r] && r < mo.size())r++; if(s[i] == mo[r]){cnt ++; r++;} if(r >= mo.size())break; } if(cnt == s.size())cout<<"Yes"<<endl; else cout<<"No"<<endl; } } int main(){ solved(); return 0; }
O(26n)代码:
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; char mo[maxn]; char pi[maxn]; int nxt[maxn][30]; int last[100]; //next[i][j]:表示模式串中第i个字符到字符z的位置 j=[a,z] void solved(){ scanf("%s",mo + 1); int n;cin>>n; int len = strlen(mo + 1); memset(last,-1,sizeof(last)); for(int i = len; i >= 0; i--){ for(int j = 1; j <= 26; j++){ nxt[i][j] = last[j];//第i个字符到字符j的位置 } last[mo[i] - 'a' + 1] = i; } while(n--){ scanf("%s",pi + 1); int len = strlen(pi + 1); int k = nxt[0][pi[1] - 'a' + 1]; //cout<<k<<endl; if(k == -1){ cout<<"No"<<endl;continue; } for(int i = 2; i <= len; i++){ k = nxt[k][pi[i] - 'a' + 1]; if(k == -1)break; // cout<<k<<endl; } if(k != -1)cout<<"Yes"<<endl; else cout<<"No"<<endl; } } int main(){ solved(); return 0; }