参考：[http://www.crazycoder.cn/]算法6.1为最简单的依次比对的方法，简单易实现，然而，却有相当大的改进余地。
参考：[http://www.crazycoder.cn/]设text长度为text_length, 被查找的字符串长patt_length，在平凡算法中，最少要比较patt_length次，而最坏为O(patt_length * text_length)
注：下面的代码从命令行读入text和pattern,如果输入含有特殊字符，需要转义。
本章内其后的代码实现基本与此相同，只是更换了sm的算法，不再重复注释。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <string.h>
char * text = NULL;
char * pattern = NULL;
char * pattern = NULL;
void usage(char * prog)
{
printf(\"Usage: %s text pattern\\n\", prog);
exit(123);
}
{
printf(\"Usage: %s text pattern\\n\", prog);
exit(123);
}
void simple_sm(char * patt, char * text, int patt_length, int text_length)
{
int i = 0, j;
while(i < text_length - patt_length +1)
{
j = 0;
while(j < patt_length && patt[j] == text[i+j])
j ++;
if(j >= patt_length)
{
printf(\"position %d\\n\", i);
printf(\"text: %s\\n\", text);
printf(\"patn: \");
for(j = 1; j <= i; j ++)
printf(\" \");
printf(\"%s\\n\", pattern);
return;
}
else
i ++;
}
printf(\"Not match\\n\");
}
[Page]{
int i = 0, j;
while(i < text_length - patt_length +1)
{
j = 0;
while(j < patt_length && patt[j] == text[i+j])
j ++;
if(j >= patt_length)
{
printf(\"position %d\\n\", i);
printf(\"text: %s\\n\", text);
printf(\"patn: \");
for(j = 1; j <= i; j ++)
printf(\" \");
printf(\"%s\\n\", pattern);
return;
}
else
i ++;
}
printf(\"Not match\\n\");
}
int main(int argc, char * argv[])
{
if(argc != 3)
usage(argv[0]);
else
{
text = argv[1];
pattern = argv[2];
}
printf(\"text: %s\\n\", text);
printf(\"patn: %s\\n\", pattern);
{
if(argc != 3)
usage(argv[0]);
else
{
text = argv[1];
pattern = argv[2];
}
printf(\"text: %s\\n\", text);
printf(\"patn: %s\\n\", pattern);
simple_sm(pattern, text, strlen(pattern), strlen(text));
return 1;
}
return 1;
}
最新评论