到了不得不学数据结构的时候了,很痛苦


​ 初入大学,对大学生活充满了期待,但又不想碌碌无为,经常会参加学校新手赛,没有什么算法基础,直接暴力解决,曾因为各种问题百思不得其解,打各种比赛也没有什么成绩,一度想要放弃学习。后来学习了渣瓦,一年没有刷题了,远离了痛苦,现在又要面对痛苦了。





利用C++方法查找重复的字符串

#include<bits/stdc++.h>
#include <string>
using namespace std;
int Index(string S,string T,int pos);
int main(){
    string S;
    string T;
    cin>>S;
    cin>>T;
    int index;
    index = Index(S,T,0);
    cout<<"index:"<<index;
}
//返回子串T在主串S第pos之后的位置,若不存在,则函数返回0
//T非空,1<=pos<=StrLength(S) 
int Index(string S,string T,int pos){
    int n,m,i;
    string sub;
    if(pos>=0){
        n = S.size();
        m = T.size();
        i = pos;
        while(i<=n-m+1){
            sub=S.substr(i,m);//取主串第i个位置,
                            //长度和T相同子串给sub
            if(sub.compare(T)!=0){
                ++i;
            } else
            return i;
        }
    }
    return 0;
}

朴素的数组匹配算法

#include<iostream> 
#include<cstring>
using namespace std;
int Index(char S[100],char T[100],int pos);
int main(){
    char S[100];
    char T[100];
    cin>>S;
    cin>>T;
    int index;
    index = Index(S,T,0);
    cout<<"index:"<<index;
}
//返回子串T在主串S第pos之后的位置,若不存在,则函数返回0
//T非空,1<=pos<=StrLength(S) 
int Index(char S[100],char T[100],int pos){
    int i = pos;    //匹配S起始位置
    int j = 0;    //字串T的起始
    while(i<strlen(S)&&j<strlen(T)){
        if(S[i]==T[j]){    
            ++i;
            ++j;
        }else{
            i=i-j+2;
            j=0;
        }
        
    }
    cout<<i<<endl;
    cout<<j<<endl;
    if(j==strlen(T)){
        return i-strlen(T);
    }else{
        return 0;
    }
    
}