4.3 朴素模式匹配算法

本文主要是介绍4.3 朴素模式匹配算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

什么是模式匹配

主串：S='wangdao'
子串：'wang'、'ang'、'ao'····（一定是主串中存在的才叫“子串”）
模式串：'gda'、'bao'（想尝试在主串中找到的串，未必存在）
串的模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置

int Index(SString S,SString T){
    int k=1;
    int i=k,j=1;
    while(i<=S.length&&j<=T.length){
        if(S.ch[i]==T.ch[i]){
            ++i;
            ++j;	//继续比较后继字符
        }else{
            k++;	//检查下一个子串
            i=k;
            j=1;
        }
    }
    if(j>T.length)
        return k;
    else
        return 0;
}

若模式串长度为m，主串长度为n，则：
匹配成功的最好时间复杂度：O(m)
匹配成功的最好时间复杂度：O(n-m+1)=O(n-m)=O(n)
直到匹配成功/匹配失败最多需要（n-m+1）*m次比较
最坏时间复杂度：O(nm)，最坏情况：每个子串的前m-1个字符都和模式串匹配，只有第m个字符不匹配
				    比较好的情况：每个子串的第一个字符就与

这篇关于4.3 朴素模式匹配算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！