Acwing第776题(字符串移位包含问题)

相关题目:

字符串移位包含问题https://www.acwing.com/problem/content/description/778/Acwing第776题(字符串移位包含问题)https://www.acwing.com/problem/content/description/778/

解题思路 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";
   }
}

上一篇:String、StringBuilder、StringBuffer的详细介绍


下一篇:[java基础] java字符串对象的"+"操作