青叶


私信TA

用户名:15005097886

访问量:4231

签 名:

等  级
排  名 1140
经  验 1612
参赛次数 0
文章发表 27
年  龄 0
在职情况 学生
学  校 福州大學
专  业

  自我简介:

方法一:滑窗法。时间是 O(n*m)

#include <iostream>
#include <cstring>
#define Max_nums 100
using namespace std;

int findSubIndex(char *str1, char* str2){
    for(int i=0; i<=strlen(str1)-strlen(str2); i++){
        int j=0;
        // 这里开个大小strlen(str2)的滑窗
        while(j<strlen(str2) && str1[i+j]==str2[j]) j++;
        if(j==strlen(str2)) return i+1;
    }
    return 0;
}

int main(){
    char str1[Max_nums],str2[Max_nums];
    while(cin>>str1>>str2){
        cout<< findSubIndex(str1, str2)<<endl;
    }
    return 0;
}



方法二:kmp算法。时间: O(m+n)

kmp算法学习:https://www.cnblogs.com/yejifeng/p/10317390.html
#include <iostream>
#include <cstring>
#define Max_nums 100
using namespace std;

void getNext(char *str, int *next){
    //生成next数组值 
    next[0] = -1;
    int k=-1, j=0;
    while(j < strlen(str)){
        if(k==-1 || str[k]==str[j])
            next[++j] = ++k;
        else
            k=next[k];
    }
}

int findSubIndex_KMP(char *str1, char *str2, int *next){
    //查找模式串str2是否为主串str1的子串
    //若是返回子串在母串中第一次出现的位置
    //若不是则输出0
    int i=0, j=0;
    int len2=strlen(str2); //strlen()返回无符号整数,不能用于和负数比较 
    while(i<strlen(str1) && j<len2){
        if(j==-1 || str1[i]==str2[j]){
            i++;
            j++;
        }
        else 
            j=next[j];
    }

    return j==strlen(str2) ? i+1-j : 0;
}



int main(){
    char str1[Max_nums],str2[Max_nums];
    int next[Max_nums];
    while(cin>>str1>>str2){
        getNext(str2, next);
        cout<<findSubIndex_KMP(str1,str2,next)<<endl;
    }
    return 0;
}


 

0.0分

0 人评分

  评论区