学习算法博客------第二章 字符串是否包含问题

出处：http://blog.csdn.net/v_JULY_v/article/details/6347454

自己实现一下：

#include <stdio.h>
#include <assert.h>

#define INVALID 0
#define TRUE 	1
#define FALSE 	0
typedef int BOOL;

//O(m*n)方法 找字串是否都在原字符串中出现
BOOL findSubstrFunc1(const char *str, const char *substr)
{
	assert(str != NULL);
	assert(substr != NULL);

//下面这句话一定注意！！！！传参数是const，将其赋值给新变量，新变量也要为const
	const char *temp = str;     
	for (;*substr != '\0'; ++substr, str = temp){
		for (;*str != '\0'; ++str){
			if(*str == *substr){
				break;
			}
		}
		if (*str == '\0'){
			return FALSE;
		}
	}
	return TRUE;
}
//没有写排序函数，这里仅仅假设传来的两个字符串都经过排序了 O(m*n)以下
BOOL findSubstrFunc2(const char *str, const char *substr)
{
	assert(str != NULL);
	assert(substr != NULL);

	while (*str != '\0' && *substr != '\0'){
		while (*str < *substr && *str != '\0'){
			++str;
		}
		if (*str == *substr){
			++str;
			++substr;
		}
		if ( *str > *substr ){
			return FALSE;
		}
	}
	if (*str == '\0' && *substr != '\0'){
		return FALSE;
	}
	else {
		return TRUE;
	}

}
//O(m+n)方法，用数组，或者hash表 找字串 是否都在原字符串出现
BOOL findSubstrFunc3(const char *str, const char *substr)
{
	assert(str != NULL);
	assert(substr != NULL);

	char hash[26] = {0};
	for (;*str != '\0'; ++str){
		hash[*str - 'A'] = TRUE;
	}

	for (; *substr != '\0'; ++substr){
		if (hash[*substr - 'A'] != TRUE){
			return FALSE;
		}
	}
	
	return TRUE;
}
#define SHIFT 3
#define MASK  0x07

void setBit(char *hash, int bit)
{
	hash[bit >> SHIFT] |= 1 << (bit & MASK);
}
void clearBit(char *hash, int bit)
{
	hash[bit >> SHIFT] &= ~ (1 << (bit & MASK));
}
char testBit(char *hash, int bit)
{
	return (hash[bit >> SHIFT] & (1 << (bit & MASK))) != 0;
}
//用bitmap 方法 找字串看是否都在原字符串中
BOOL findSubstrFunc3_BITMAP(const char *str, const char *substr)
{
	assert(str != NULL);
	assert(substr != NULL);

	char hash[4] = {0};
	for (; *str != '\0'; ++str){
		setBit(hash, *str - 'A');
	}

	for (; *substr != '\0'; ++substr){
		if (testBit(hash, *substr - 'A') != 1)
			return FALSE;
	}
	
	return TRUE;
}
//找出字符串中 第一个只出现一次的字符，dcldallf 就打印'd'一个
BOOL findFirstAppear(const char *str)
{
	assert(str != NULL);

	char hash[26] = {0};
	for (; *str != '\0'; ++str){
		if (hash[*str - 'A'] != TRUE){
			hash[*str - 'A'] = TRUE;
		}
		else {
			printf("%c\n", *str);
			return TRUE;
		}
	}

	return FALSE;
}
//字符串拷贝 由调用者保证目标buf有足够位置
void strCOPY(char *des, const char *src)
{
	assert(des != NULL);
	assert(src != NULL);

	while ((*des++ = *src++) != '\0')
		;
}
//下面是别人实现的一种方式，你没有想到，以后要记得 这种拷贝的函数 很多要弄成链式的
//10分  
//为了实现链式操作，将目的地址返回，加3分！  
char * strcpy( char *strDest, const char *strSrc )   
{  
    assert( (strDest != NULL) && (strSrc != NULL) );  
    char *address = strDest;   
    while( (*strDest++ = * strSrc++) != '/0' );   
    return address;  
}