牛客15870 好位置 KMP暴力循环

题目连接：牛客15870 好位置 KMP/循环 传送门

题目描述

给出两个串s和x 定义s中的某一位i为好的位置，当且仅当存在s的子序列 定义s中的某一位i为好的位置，当且仅当存在s的子序列 满足y=x且存在j使得i=kj成立。问s中是否所有的位置都是好的位置。

输入描述

一行两个字符串s，x,这两个串均由小写字母构成。 1 <= |s|, |x| <= 200000

输出描述

Yes表示是。 No表示不是。

题解

两个串s和x，就是s中的任意一个字符的左右连续字符都能和x匹配，匹配成功yes，不成功no。

方法1 KMP匹配并记录匹配成功的位置， 通过匹配成功的次数和字符串y的长度可计算出匹配成功的长度总和，若总和小于字符串x则No 若匹配成功的位置差大于字符串y的长度，则No

#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; const int MAX=1e6+7; int nt[MAX]; vector<int>p; void kmp_next(string str,int next[]) { int len=str.size(); next[0]=-1; for(int i=0,j=-1;i<len;) { if(j==-1||str[i]==str[j]) { next[++i]=++j; } else j=next[j]; } } int kmp(string s,string str,int next[]) { int l1=s.size(),l2=str.size(),f=0; for(int i=0,j=0;i<l1&&j<l2;) { if(j==-1||s[i]==str[j]) { i++,j++; } else j=next[j]; if(j==l2){ j=next[j]; p.push_back(i); } } } int main() { ios::sync_with_stdio(0);cin.tie(0), cout.tie(0); string s,str; cin>>s>>str; kmp_next(str,nt); kmp(s,str,nt); int f=0; if(p.size()*str.size()<s.size())f=1; for(int i=1;i<p.size();i++) { if(p[i]-p[i-1]>str.size()){ f=1;break; } } if(f)cout<<"No"; else cout<<"Yes"; return 0; }

方法2 因为符合条件的字符串x都是由字符串y组成，故可循环暴力匹配

#pragma GCC optimize(2) #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0);cin.tie(0), cout.tie(0); string s,str; cin>>s>>str; int l1=s.size(),l2=str.size(),f=0; for(int i=0;i<l1;i++) { if(s[i]!=str[i%l2]){ f=1;break; } } if(f)cout<<"No"; else cout<<"Yes"; return 0; }