BF（Brute-Force）算法

一、问题引入

模式匹配算法是对两个字符串进行比较匹配的算法。

在两个串中字符逐个匹配，若完全匹配，则返回位置，否则返回-1。

二、解决过程

#include <stdio.h>

int index_bf(char *S, char *T, int pos)
{
	int S_len = strlen(S);
	int T_len = strlen(T);
	if (S_len == 0 || T_len == 0)
		return -1;
	if (pos < 0 || pos > S_len-1)
		return -1;
	int i = pos, j = 0;
	while (i < S_len && j < T_len)
	{
		if (S[i] == T[j])
		{
			++i;
			++j;
		}
		else
		{
			i = i - j + 1; // i 移到最近一次相等的位置
			j = 0;         // j 移到起点位置
		}
	}
	if(j == T_len) // 若字符串S和T全部比较完后，且j的位置移到T的末尾，则匹配成功
		return (i - T_len);
	else
		return -1;
}

int main(void)
{
	char S[] = {"hello world"};
	char T[] = {"heo"};
	int index; // index从0开始
	printf("S_String：%s\n", S);
	printf("T_String：%s\n", T);
	if (-1 == ( index = index_bf(S, T, 0)))
	{
		printf("Not found\n");
	}
	else
	{
		printf("Found, index is %d\n", index);
	}
	return 0;
}