当前位置:编程学习 > C/C++ >>

朴素字符串匹配——算法导论

字符串T = abcabaabaadac, 字符串P = abaa,判断P是否是T的子串,就是字符串匹配问题了,T叫做文本(Text),P叫做模式(Pattern).
 
算法思想
朴素的字符串匹配过程可以形象的看成一个包含模式的“模板”P沿文本T移动,同时对每个位移注意模板上的字符是否与文本中的相应字符相等。外层循环的次数最多为len(s) - len(p),内层循环的次数最多为len(p).
最坏情况下的时间复杂度:O((len(T) - len(P) + 1) * len(P))
两个for循环,代码比较简单,但是效率很低
 
算法代码
[cpp]  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
  
void main()  
{  
    char part[20], str[50];  
    int i, flag, j, len_p, len_s, k;  
  
    while(scanf("%s %s", part, str) != EOF)  
    {  
        //获取字符串长度  
        len_p = strlen(part);  
        len_s = strlen(str);  
          
        //朴素字符串匹配算法  
        for(i = 0, flag = 0; i < len_s - len_p + 1; i ++)  
        {  
            for(j = i, k = 0; part[k] == str[j] && part[k] != '\0' && str[k] != '\0'; j ++, k ++)  
            {  
            }  
            if(k > 0 && part[k] == '\0')  
            {  
                flag = 1;  
                break;  
            } http://  
        }  
  
        //输出匹配成功or失败  
        if(flag)  
            printf("匹配成功,匹配位置是:%d\n", i + 1);  
        else  
            printf("匹配失败!\n");  
    }  
}  
 
 
算法记号与术语
 用 Σ* 表示用字母表Σ中的所有有限长度的字符串的集合
字符串x的长度用|x|表示
x和y的连接表示为xy,长度为|x| + |y|
x = yw, y是x的前缀,w是x的后缀
 
补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,