08_ strand

strand

Empty string ：“” —>“\0”
Space string ：" " —>" \0"
Substring ：
True string ：

Suitable for the following string ：

Not suitable for the following string ：

1.BF Algorithm （ Simple algorithm ）

// Simple algorithm  BF Algorithm  ：1. Run backwards at the same time  2. If equal i++ j++ 3. If it's not equal i=i-j+1 j=0 
int BF_Search(const char* str, const char* sub, int pos)// From the main string pos The subscript starts looking back for the substring 
{
    
	assert(str != NULL && sub != NULL && pos >= 0 && pos < strlen(str));
	if (str == NULL || sub == NULL || pos < 0 || pos >= strlen(str))
	{
    // \0
		return -1;
	}

	int lenstr = strlen(str);//lenstr  Save the length of the main string 
	int lensub = strlen(sub);//lensub  Save the length of the substring 
	int i = pos; //i  Save the subscript of the main string matching 
	int j = 0; //j  Save the subscript of substring matching 

	while (i < lenstr && j < lensub)// When the main string and string are not out of range , The cycle continues 
	{
    
		if (str[i] == sub[j])// If equal   be i and j meanwhile ++,  Judge the next character 
		{
    
			i++;
			j++;
		}
		else // Representative mismatch   If it doesn't match   Then let i Go back to the next position before this match   and j Zeroing 
		{
    
			i = i - j + 1;//
			j = 0;// The order of these two lines of code cannot be reversed 
		}
	}
	// here while The loop ends   There are only two possibilities   You need to judge i and j Who walked to the tail 
	if (j >= lensub)// If the string j Go to the tail   It means that the match is successful 
	{
    
		return i - j;// If the match is successful   Then return the position before this successful match 
	}

	// If the string j Did not go to the tail   That means the main string doesn't have what the string wants   Then return to -1
	return -1;
}

2.KMP Algorithm （ Only related to substring ）

Substring mismatch 2 In this case ：

seek next Array ：

Code implementation ：

int* Get_next(const char* sub)//next Arrays are only related to substrings 
{
    
	//assert
	int lensub = strlen(sub);//lensub Save the length of the substring 

	int* next = (int*)malloc(sizeof(int) * lensub);// Apply for an equal length next Array to hold each of them K value 
	assert(next != NULL);

	next[0] = -1;//next The first two spaces of the array have fixed values  -1 0
	next[1] = 0;

	int j = 1;//j Saved known k The subscript 
	int k = 0;

	// Push through the unknown  j Is known   be j+1 It's unknown   and j+1 To judge the legitimacy of （ Give Way j+1<lensub that will do ）
	while (j + 1 < lensub)// to next Each space of the array is assigned an appropriate value  
	{
    
		if ((k == -1) || sub[j] == sub[k])// Two equal or k Back to -1
		{
    
			next[++j] = ++k;
			/*k++; j++; next[j] = k;*/
		}
		else
		{
    
			k = next[k];//k Back to the right place 
		}
	}

	return next;// take malloc Applied next Throw out the array 
}

int KMP_Search(const char* str, const char* sub, int pos)// From the main string pos The subscript starts looking backwards for the string 
{
    
	assert(str != NULL && sub != NULL && pos >= 0 && pos < strlen(str));
	if (str == NULL || sub == NULL || pos < 0 || pos >= strlen(str))
	{
    
		return -1;
	}

	int lenstr = strlen(str);//lenstr  Save the length of the main string 
	int lensub = strlen(sub);//lensub  Save the length of the string 
	int i = pos; //i  Save the subscript when the main string matches 
	int j = 0; //j  Save the subscript when the substring matches 

	int* next = Get_next(sub);//next Arrays are only related to substrings 

	while (i < lenstr && j < lensub)// When the main string and string are not out of range , The cycle continues 
	{
    
		if ((j == -1) || str[i] == sub[j])// If equal   be i and j meanwhile ++,  Judge the next character 
		{
    
			i++;
			j++;
		}
		else // Representative mismatch   If it doesn't match   Then let i Go back to the next position before this match   and j Zeroing 
		{
    
			//i = i-j+1;//
			//j = 0;// The order of these two lines of code cannot be reversed 
			j = next[j];//j Return to the right place next[j]
		}
	}
	// here while The loop ends   There are only two possibilities   You need to judge i and j Who walked to the tail 
	if (j >= lensub)// If the string j Go to the tail   It means that the match is successful 
	{
    
		return i - j;// If the match is successful   Then return the position before this successful match 
	}

	// If the string j Did not go to the tail   That means the main string doesn't have what the string wants   Then return to -1
	return -1;
}