图：求子串位置的定位函数

书中的算法思想是这样的：分别利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置。算法的基本思想是：从主串S的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字符，否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串中的序号，否则称匹配不成功，函数值为零。<br />

C语言解答

#include <stdio.h>
int main(){
	int i,j,k,n,flag;
	char str[100],sub[100];
//	freopen("1.txt","r",stdin);
	while(scanf("%s %s",str,sub)!=EOF){
		i=j=0;
		while (str[i]&&sub[j])
		{
			printf("%c",str[i]);
			if (str[i]==sub[j])
			{
				i++;
				j++;
			}else{
				i=i-j+1;
				j=0;
			}
		}
		printf("\n");
		if (!sub[j])
		{
			printf("%d\n",i-j+1);
		}else{
			printf("0\n");
		}
	}
//	fclose(stdin);
	return 0;
}

C++解答

#include <stdio.h>
#include <string.h>

#define MAXSTRLEN 100
typedef char SString[MAXSTRLEN+2];

void InputString(SString &str) {
	// 读取字符串
	scanf("%s", str + 1); // 首先用scanf读取字符串
	str[0] = strlen(str + 1); // 求出字符串的长度并保存在str[0]中
}

int Index(SString S, SString T, int pos) { // 算法4.5
	// 返回子串T在主串S中第pos个字符之后的位置。
	// 若不存在，则函数值为0。
	// 其中，T非空，1≤pos≤StrLength(S)。
	int i = pos;
	int j = 1;
	while (i <= S[0] && j <= T[0]) {
		putchar(S[i]);		// 只要添加这一句输出相应的字符即可
		if (S[i] == T[j]) { // 继续比较后继字符
			++i;
			++j;
		} else { // 指针后退重新开始匹配
			i = i - j + 2;
			j = 1;
		}
	}
	if (j > T[0]){
		return i - T[0];
	}
	else
		return 0;
} // Index

int main(){
	int i;
	SString S, T;			// 定义存储两个字符串的变量
	int index = 0;			// 存储下标
	for(i=0; i<3; i++){
		InputString(S);		// 读取两个字符串
		InputString(T);
		index = Index(S, T, 1);	// 定位子串
		printf("\n%d\n", index);// 输出子串的下标
	}

	return 0;
}