#include?“HString.h“

//?創建一個空串
HString?createString（）{
	HString?hs;
	InitString（&hs）;
	return?hs;
}

Status?InitString（HString?*T）{
	T->ch?=?NULL;
	T->len?=?0;
	return?OK;
}

Status?StrAssign（HString?*T?char?*chars）{
	//?生成一個其值等于串常量chars的串T
	//?臨時變量
	int?len=0i=0;
	char?*c;
	if（T->ch）?
		free（T->ch）;
	//?計算chars的長度
	for（len=0c=chars;?*c;?++c）
		++len;
	
	if（!len）{T->ch?=?NULL;?T->len?=?0;}
	else
	{
		if（!（T->ch?=?（char*）malloc（len*sizeof（char））））
			exit（0）;
		for（i=0;i			T->ch[i]?=?chars[i];
		T->len?=?i;
	}
	return?OK;
}	

//?返回S的元素個數，稱為串的長度
int?StrLength（HString?S）{
	return?S.len;
}

int?StrCompare（HString?SHString?T）{
	//?若S>T，則返回值>0；若S=T，則返回值=0；若S	int?i=0;
	for（i=0;i		if（S.ch[i]!=T.ch[i]）?return?S.ch[i]-T.ch[i];
	}
	return?S.len?-?T.len;
}

Status?ClearString（HString?*S）{
	//?將S清為空串
	if（S->ch）?{
		free（S->ch）;?
		S->ch?=?NULL;
	}
	S->len?=?0;
	return?OK;
}

Status?Concat（HString?*T?HString?S1?HString?S2）{
	//?用T返回由S1和S2聯接而成的新串
	int?i=0;
	if?（T->ch）?free（T->ch）;
	if（!（T->ch?=?（char*）malloc（（S1.len?+?S2.len）*sizeof（char））））
		exit（0）;
	//連接第一個串
	for（i=0;ich[i]?=?S1.ch[i];
	//連接第二個串
	for（i=0;ich[i?+?S1.len]?=?S2.ch[i];
	T->len?=?S1.len?+?S2.len;
	return?OK;
}

Status?Substring（HString?*Sub?HString?S?int?pos?int?len）{
	//?用Sub返回串S的第pos個字符起長度為len的子串。
	//?其中，1<=pos<=StrLength（S）且0<=len<=StrLength（S）-pos+1
	int?i=0;
	if（pos??S.len?||?len??S.len?-?pos?+1）
		return?ERROR;
	if（Sub->ch）free（Sub->ch）;
	if（!len）?{Sub->ch?=?NULL;?Sub->len?=?0;}
	else
	{
		Sub->ch?=?（char*）malloc（len*sizeof（char））;
		for（i=0;i			Sub->ch[i]?=?S.ch[i+pos-1];
		Sub->len?=?len;
	}
	return?OK;
}

Status?StrCopy（HString?*des?HString?src）{
	//?des為目標串，src為源串
	//?把src拷貝到des
	int?i=0;
	if（des->ch）?free（des->ch）;
	des->ch?=?（char?*）malloc（sizeof（char）*src.len）;
	if（!des->ch）?exit（0）;
	for（i=0;i	{
		des->ch[i]?=?src.ch[i];
	}
	des->len?=?src.len;
	return?OK;

}

//?返回子串T在主串S中第pos個字符之后的位置。若不存在，則函數值為0
//?其中，T非空，1<=pos<=StrLength（S）.
int?Index（HString?S?HString?Tint?pos）{
	int?i=posj=1;
	while（i<=S.len&&j<=T.len）{
		if（S.ch[i-1]?==?T.ch[j-1]）{
			++i;++j;
		}?else?{
			i=i-j+2;?j=1;
		}
	}
	if（j>T.len）return?i-j;
	else?return??0;
}

int?Index_KMP（HString?S?HString?T?int?pos）{
	int?i=posj=1;
	int?*next?=?（int?*）malloc（sizeof（int）*（T.len+1））;
	get_nextval（T?next）;
	while（i<=S.len?&&?j<=T.len）{
		if（j==0?||?S.ch[i-1]?==?T.ch[j-1]）{
			++i;?++j;
		}
		else?
			j?=?next[j];
	}
	free（next）;
	if（j>T.len）?return?i-j;
	else?return?0;
}

void?get_next（HString?T?int?next[]）
{
	//求模式串的next函數值并存入數組next
	int?i=1j=0;?
	next[1]=0;
	while（i		if（j==0||T.ch[i-1]?==?T.ch[j-1]）{
			++i;++j;next[i]?=?j;
		}?else?{
			j?=?next[j];
		}
	}
}

void?get_nextval（HString?T?int?nextval[]）
{
	//求模式串的next函數值并存入數組ne