数据结构---字符串

串的定义

串是由零个或多个字符顺序排列组成的有限序列

空串

长度为零的串

空白串

由一个或多个空格组成的串

字符串匹配问题

朴素模式匹配

模式匹配的查找过程 (Find):

给定两个字符串变量S和P，其中目标S有n个字符，模式P有m个字符，m<=n。从S的给定位置（通常为S的第一个字符）开始，搜索模式P，如果找到，返回模式P的第一个字符在S中的位置；如果没找到（即S中没有P），则返回-1 。

以下为 StringMatching( S, P ) 的 C++ 代码, S为目标串, P为模式串, 返回S中首个P子串的位置

int StringMatching(string S, string P)
{
	unsigned int i = 0;
	while(i <= S.size() - P.size())
	{
		unsigned int j = 0;
        //字符匹配成功 && j没有越界
		while(S[i] == P[j] && j < P.size())
		{
			i = i + 1;
			j = j + 1;
		}
		if(j == P.size())
		{
            //返回坐标
			return i - j;	
		} 
        //坐标后移
		i = i - j + 1;
	}
	return -1;
}

朴素模式匹配算法时间复杂度

最好:m 最坏: m(n-m+1) = O(nm)

平均时间复杂度: O(n*m)

KMP算法

时间复杂度: O(m+n)

KMP算法充分利用了目标字符串ptr的性质（比如里面部分字符串的重复性，即使不存在重复字段，在比较时，实现最大的移动量).

计算长度为m的next数组

next数组的含义就是存放一个固定字符串的最长前缀和最长后缀相等的长度

下面是求解next数组的 C++ 代码:

int* cal_next(char* ptr, int plen)
{
	int* next = new int[plen];
    next[0] = -1;
    int prefix_len = -1;
    int i = 1;
    while(i < plen)
    {
        if(ptr[i] == ptr[prefix_len + 1])
        {
            prefix_len = prefix_len + 1;
            next[i] = prefix_len;
            i = i + 1;
        }
        else
        {
            if(prefix_len > -1)
            {
                prefix_len = next[prefix_len];
            }
            else
            {
                next[i] = -1;
                i = i + 1;
            }
        }
    }
	return next;
}

//或者下面的也可以求next数组,原理一样, 就是不一样的代码而已
int* cal_next(char* ptr, int plen)
{
    int* next = new int[plen];
    next[0] = -1;
    int k = -1;
	for(int i = 1; i < plen; i++)
    {
        while(k > -1 && ptr[k+1] != ptr[i])
        {
            k = next[k];
        }
        if(ptr[k+1] == ptr[i])
        {
            k = k + 1;
        }
        next[i] = k;
    }
   	return next;
}

下面是KMP的 C++ 实现代码, 同样给出两种形式的代码:

int KMP(char* str, char* ptr, int slen, int plen)
{
    int* next = cal_next(ptr, plen);
    int j = -1;
    int i = 0;
    while(i < slen)
    {
  		if(ptr[j+1] == str[i])
        {
            i = i + 1;
            j = j + 1;
        }
        else
        {
            if(j > -1)
            {
                j = next[j];
            }
            else
            {
                i = i + 1;
            }
        }
        if(j == plen - 1)
        {
            return i-j;
        }
    }
    return -1;
}


int KMP(char* str, char* ptr, int slen, int plen)
{
	int* next = cal_next(ptr, plen);
    int j = -1;
    for(int i = 0; i < slen; i++)
    {
        while(j > -1 && ptr[j+1] != str[i])
        {
            j = next[j];
        }
        if(ptr[j+1] == str[i])
        {
            j = j + 1;
        }
        if(j == plen - 1)
        {
            return i-j;
        }
    }
   	return -1;
}