C基础——布鲁特福斯算法（字符串匹配）探机博客

前言：

想要进学校软件小组，靠RP做选择题过了初审，实在是丢人的很。话说国庆那几天瞎忙活了，包括搬家至HWL数据全被锁，文章丢失，百度索引归0…… 只怪现实太残忍。一开始学长出了个匹配字符串的题目，自己瞎忙活了一下午也没有实现，果断在初审的时候第二题求a——b之间的质数，虽然有些印象但是果断不会做，最后一题是量身准备的“字符串匹配”,因为我是猪，又被秒了。

正文：

题目内容：

/*题目要求：实现findString函数，childString已知为"child"，parentString已知为"parent has a child".
判断childeString是否为parentString的子串（即判断parentString是否包含childString），
若是则返回childString在parentString的起始位置
若不是则返回false*/
//禁止修改findString函数之外的任何部分
#include
#include
#define false 0
int findString(char childString[],char parentString[])
{ int i,z,m;
i=strlen(childString);
z=strlen(parentString);
}
int main()
{
	char childString[]={'c','h','i','l','d','\0'};
	char parentString[]={'p','a','r','e','n','t',' ','h','a','s',' ','a',' ','c','h','i','l','d','\0'};
	int result=findString(childString,parentString);
	if(result)
	{
		printf("%s 是 %s的子串，起始位置为%d\n",childString,parentString,result);
	}
	else
	{
		printf("%s 不是 %s的子串.\n",childString,parentString,result);
	}
	return 0;
}

其实这个题火狼博客博主灰狼婆婆曾经给我发过链接地址，让我去AC，当时没想那么多，以为自己好牛逼（主要是题目看起来好像很简单），被秒表示自己灰常活该。于是乎匹配子字符串好像有个叫——布鲁特福斯的很牛逼的样子，弄了个什么算法，身为凡人的我实在想不出来。

布鲁特福斯算法：

布鲁特福斯Brute-Force算法是一种（朴素的模式匹配）算法。

基本的算法思想：从主串的第一个字符起与模式串的第一个字符进行比较，若相等，则继续逐字符进行后续比较，如果不成立从主串第二个字符开始，直至模式串中每个字符依次和主串中一个连续的字符序列相等为止，此时称匹配成功。依次延后匹配，如果不能在主串中找到与模式串相同的子串，则匹配失败。

//S为主串，T为模式串，pos为从主串中开始查找的位置，T若不是S的子串，则返回-1值；

int StrIndex(char* s,int pos,char* t)//
{
    /*
    i:指向主串s中当前比较的字符
    j:指向子串t中当前比较的字符
    start:记录每趟比较时在主串中的起点
    */
    int i,j,start;
    int LenS = strlen(s);
    int LenT = strlen(t);
    if(LenT==0)
        return 0;        //模式串是空串时是任意串的匹配串
    start = pos;
    i = start;
    j = 0;        //主串从pos开始，模式串从0开始
    while(i<LenS&&j<LenT) {
if(s[i] == t[j])
 { i++; j++; //当前字符串对应相等时推进 } else
 //不等时回溯
 { start++; i = start; j = 0; //主串从start+1开始，模式串从头开始 }
 }
if(j>=LenT)
        return start;        //匹配成功时，返回匹配起始位置
    else
        return -1;
}

感谢狼婆婆提供的正确代码，网上有点扯，狼婆婆手入05年3月写。学习要向狼婆婆看齐。自己还没码一遍呢。