朴素字符串匹配

模型算法

复习串的朴素模式匹配算法

朴素字符串匹配，为什么说他朴素，因为匹配的过程很”笨“很实诚的一个过程 ：）

• 模式匹配 ：
  子串定位运算，在主串中找出子串出现的位置。
  在串匹配中，将主串 S 称为目标(串)，子串 T 称为模式(串)。如果在主串 S 中能够找到子串 T， 则称匹配成功，返回 第一个 和 子串 T 中 第一个字符 相等 的 字符 在主串 S 中的 序号，否则，称匹配失败，返回 0。

• 算法思想：
  从主串 S 的第 pos 个字符起和模式 T 的第一个字符比较之，若相同，则两者顺次的去比较后续的每一个字符，否则从主串 S 的下一个字符起再重新和模式 T 的字符比较之。 （为什么说它朴素，就是因为笨，因子串和主串的每躺比较，当发现匹配不对，则主串的指针要回溯到上次开始比较的字符处的下一个字符处，去重新比一遍！费劲）

• 分析时间复杂度
  最坏的时候，最后匹配成功，比如，0000000000001 和 00001 ，比较每次都在00001的1开始不匹配，指针回溯到开头，主串也回溯 i-j+1，若模式子串的长度是m,目标串的长度是n，

  这时最坏的情况是每遍比较都在最后出现不等，即每遍最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法为 o（m*n），虽然，朴素的模式匹配，时间复杂度比较大，但是实际中，一般情况（除非模式串和主串之间存在很多的部分匹配的时候，因为此时每遍需要比较的次数很多，相乘不能近似），真正的执行时间是近似于o（n+m ）的，故当今仍然有他的用处！

  如下代码亲测可用：

int getLength(char *str)
{
    int i = 0;
    while ('\0' != str[i]) {
        i++;
    }
    return i;
}
int strCompare(char *strMain, char *strSub, int index)
{
    int iMain = index;
    int jSub = 0;
    int lenMain = getLength(strMain);
    int lenSub = getLength(strSub);
    while ((iMain >= 0 && iMain <= lenMain - 1) && ((jSub >= 0 && jSub <= lenSub - 1))){
        if (strMain[iMain] == strSub[jSub]) {
            iMain++;
            jSub++;
        }else{
            iMain = iMain - jSub + 1;
            // 回到主串的下一个位置起，开始比较，每次重新开始顺次比较，
            //[012345678] :主串index
            // xyz124abc  :主串
            //   [012]    :子串index
            //    123     :子串
            // 当前主串的回溯位置： 3-0，4-1，5-2 = 3 也就是：iMain - jSub
            //回到主串的下一个位置起，开始比较，每次重新开始顺次比较， ij 走的长度是一样的，如果从0开始，那么相减之后，故+1到下一位，如果是从1开始存，那么+2到下一位。
            jSub = 0;
        }
    }
    //如果匹配 ok，肯定子串先比完。
    if (jSub > lenSub - 1) {
        return iMain - lenSub;//得到的就是匹配 ok 后，主串里第一个和模式串第一个字符匹配的字符的位置
    }else{
        return 0;//匹配失败
    }
}
int main(int argc, const char * argv[]) {
    char *str1 = "sawtsafvda";
    char *str2 = "safv";
    int i = strCompare(str1, str2, 0);
    printf("%d\n", i);
    return 0;
}

http://www.cnblogs.com/kubixuesheng/p/4322410.html