相关题目:
解题思路 1:
将两个主串连接到一起,不用进行循环移位,随后进行字符串的模式匹配,此算法节省了空间和时间,使其大大地优化。
相关代码 1:
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
string s1,s2;
int i=0;
int j=0;
int temp=i; //temp储存了最先开始匹配字符串s2所对应的s1所在的位置。
cin>>s1>>s2;
if(s1.length()<s2.length()){
swap(s1,s2);
}
s1=s1+s1; //这个是我之前没有想到的。看了y总的视频后悟到的。
//暴力匹配算法 自己想的,和网上的可能会有点不一样。
while(i<s1.length()&&j<s2.length()){
if(s1[i]==s2[j]){
i++;
j++;
}
else{
j=0;
i=temp+1; //最先开始匹配字母的位置+1。
temp=i; //立即更新最先开始匹配字母的位置。
}
}
if(s2.length()==j){
cout<<"true";
}
else{
cout<<"false";
}
}
解题思路 2:
按照我们正常人的想法,移位一次,进行一次模式匹配,重复s1.length()次,因为第s1.length()+1时,此时的字符串s1恢复成最初的模样。
相关代码 2:
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
string s1,s2;
int i=0;
int j=0;
int flag=0;
int temp=i; //temp储存了最先开始匹配字符串s2所对应的s1所在的位置。
cin>>s1>>s2;
if(s1.length()<s2.length()){
swap(s1,s2);
}
for(int k=0;k<s1.length();k++){
//将主串移一位。
char a=s1[0];
for(int l=1;l<s1.length();l++){
s1[l-1]=s1[l];
}
s1[s1.length()-1]=a;
//暴力匹配算法 自己想的,和网上的可能会有点不一样。
while(i<s1.length()&&j<s2.length()){
if(s1[i]==s2[j]){
i++;
j++;
}
else{
j=0;
i=temp+1; //最先开始匹配字母的位置+1。
temp=i; //立即更新最先开始匹配字母的位置。
}
}
if(s2.length()==j){
cout<<"true";
flag=1;
break;
}
else{
i=0;
j=0;
}
}
if(flag==0){
cout<<"false";
}
}