数据结构-定位子串 （C++代码） 两种方法：滑窗法和kmp法

方法一：滑窗法。时间是 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;
}