串的定义及朴素的模式匹配算法

ADT 串(string)
Data
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
    StrAssign(T,*chars):生成一个其值等于字符串常量chars的串T。
    StrCopy(T,S):串S存在，由串S复制到串T。
    ClearString(S)：串S存在，将串清空。
    StringEmpty(S):若串S为空，返回true，否则返回false。
    StrLength(S):返回串S的元素个数，即串的长度。
    StrCompare(S,T):若S>T,返回值大于0，若S=T，返回值等于0，若S<T，返回值小于0。
    Concat(T,S1,S2):用T返回S1和S2连接而成的新串。
    SubString(Sub,S,pos,len):S存在,1≤pos≤StrLength（S）,且			                                0≤1en≤StrLength（S）-pos＋1,用Sub返回串S的第                              pos个字符起长度为1en的子串。
    Index(S,T,pos):串S和T存在，T是非空串，1≤pos≤StrLength(S)。若主串S中存在和					  串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位				   置，否则返回0。
    Replace(S,T,V):串S,T,V存在，T是非空串。用V替代主串中S中出现的所有与T相等的不					 重叠的子串。
    StrInsert(S,pos,T):串S和T存在，1≤pos≤StrLength(S)+1。在串S的第pos个字符						 之前插入串T。
    StrDelete(S,pos,len):串S存在，1≤pos≤StrLength(S)+1。从串S中删除第pos个字						    符起长度为len的子串。
endADT

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(String s, String T, int pos){
    int n,m,i;
    String sub;
    if(pos>0){
        n = StrLength(S);  // 得到主串S的长度
        m = StrLength(T);  // 得到子串T的长度
        i = pos;
        while(i<=n-m+1){
            SubString(sub,S,i,m);  // 取子串第i个位置开始长度与T相等的字串给sub
            if(StrCompare(sub,T) != 0){  // 如果两串不相等
                ++i; 
            }else{  // 如果两串相等
                return i;  // 返回i值
            }
        }
    }
    return 0;  // 若无子串与T相等，返回0
}

/* 返回串的元素个数 */
int StrLength(String S)
{ 
	return S[0];
}

/* 用Sub返回串S的第pos个字符起长度为len的子串。 */
Status SubString(String Sub,String S,int pos,int len)
{
	int i;
	if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
		return ERROR;
	for(i=1;i<=len;i++)
		Sub[i]=S[pos+i-1];
	Sub[0]=len;
	return OK;
}

/*  初始条件: 串S和T存在 */
/*  操作结果: 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
int StrCompare(String S,String T)
{ 
	int i;
	for(i=1;i<=S[0]&&i<=T[0];++i)
		if(S[i]!=T[i])
			return S[i]-T[i];
	return S[0]-T[0];
}

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/* 其中,T非空,1≤pos≤StrLength(S)。 */
int Index(String S, String T, int pos){
    int i = pos;	/* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
    int j = 1;				/* j用于子串T中当前位置下标值 */
    while (i <= S[0] && j <= T[0]){ /* 若i小于S的长度并且j小于T的长度时，循环继续 */
        if (S[i] == T[j]){ 	/* 两字母相等则继续 */
            ++i;
            ++j;
        }else{ 				/* 指针后退重新开始匹配 */
            i = i-j+2;		/* i退回到上次匹配首位的下一位 */
            j = 1; 			/* j退回到子串T的首位 */
        }
    }
    if (j > T[0]){
        return i-T[0];
    }else{
        return 0;
    }
}