[数据结构与算法]数据结构--串

串

1、串的定义

子串：Fisch
主串：Fisch.com

index(S,T,pos)

12345678
345
pos则为3

2、BF算法

首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则比较S[2]和T[1]，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。

// 返回子串T在主串S中第pos个字符之后的位置
// 若不存在，则返回0
// T非空，1 <= pos <= strlen(S)
// 注意：我们这里为了表述方便，字符串使用了第一个元素表示长度的方式。

int index( String S, String T, int pos )
{
        int i = pos;        // i用于主串S中当前位置下标
        int j = 1;                // j用于子串T中当前位置下标
        
        while( i <= S[0] && j <= T[0] )        // i或j其中一个到达尾部即终止搜索！
        {                                                                                                                                                                                                                                                                                                
                if( S[i] == T[i] )        // 若相等则继续下一个元素匹配
                {
                        i++;
                        j++;
                }
                else                                // 若失配则j回溯到第一个元素从新匹配；
                {
                        i = i-j+2;                // i回溯到***上次匹配首位的下一个元素***，这是效率低下的关键！
//1231212345678； 12345； 当i=3，j=3时； 让i=3-3+2=2,j=1;
                        j = 1;
                }
        }
        
        if( j > T[0] )
        {
                return i - T[0];
        }
        else
        {
                return 0;
        }
}

3 KMP算法

一、思想： 主串指针不回溯，模式串向后滑动至某个位置上。

二、对模式串进行next数组定位的三种情况：

1、第一个字符不相等，令next = 0；

2、没有前缀和后缀相等的情况

3、存在前缀和后缀相等

三、求next函数值
i为后缀，j为前缀
a b a b e b
0 1 1 2 3 1
①i = 1，j = 0；i++ j++；next1 = 0；初始条件
②i = 2，j = 1；next2 = 1；第一次循环else
③T2 ！= T1；j = next1 = 0；第二次循环
④i++ j++；i = 3，j = 1；next3 = 1；第三次循环else
⑤T3 == T1；i = 4， j = 2；next4 = 2
⑥T4 == T2； i ++, j++ ；i = 5，j = 3；next[5] = k = 3；
⑦T5 ！= T3；j = next3 = 1；
⑧T5 ！= T1；j = next1 = 0；

#include <stdio.h>

typedef char* String;

void get_next( String T, int *next) 
{
	int i = 1;//i为后缀 
	int j = 0;//j为前缀
	next[1] = 0;
	while (i < T[0] )
	{
		if( 0 == j || T[i] == T[j])//j = 0为了避免有next[0]出现； 
		{
			i++;
			j++;
			next[i] = j;//相等的话就可以检查前缀后面的位置 
		}
		else
		{
			j = next [j]; //为了让j回溯到前缀位置，i不动。 
		}
	}//前缀是固定的，后缀是相对的。 
}

//返回子串T在主串S第pos个字符之后的位置；
//若不存在，则返回0 
int Index_KMP( String S, String T, int pos) 
{
	int i = pos;
	int j = 1;
	int next[255];
	
	get_next( T, next );
	
	while( i< S[0] || i < T[0])
	{
		if( S[i]== T[j])
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if( j > T[0])
	{
		return i - T[0];
	}
	else
	{
		return 0;
	}
}

int main()
{
	char str[255] = "ababaaaba";
	int next[255];
	int i = 1;
	
	str[0] = 9;
	
	get_next(str, next);
	
	for( i = 1; i < 10; i++)
	{
		printf(" %d", next[i]);
	}
	return 0;
}