【資料結構】串的模式比對-BF算法

目錄

串

定義

串的建立

串的比較

模式比對

BF算法

概述

BF代碼

性能

串

定義

串（或字元串）是由零個或多個字元組成的有限序列。

串的建立

#define MaxSize 100

typedef struct {
	char data[MaxSize];
	int Length;
}SqString;


int StrAssign(SqString &s,char cstr[])
{
	s.Length = 0;
	while ((s.Length < MaxSize) && (cstr[s.Length] != '\0'))
	{
		s.data[s.Length] = cstr[s.Length];
		s.Length++;
	}
	return s.Length;
}
           

串的比較

int Strcmp(SqString s, SqString t)
{
	int i, comlen;
	if (s.Length < t.Length)comlen = s.Length;
	else comlen = t.Length;

	for (i = 0; i < comlen; i++)//先比較相同長度的部分
	{
		if (s.data[i] > t.data[i])return 1;
		else if (s.data[i] < t.data[i]) return -1;
	}
	if (s.Length == t.Length)return 0;
	else if (s.Length > t.Length)return 1;
	else return -1;
}
           

模式比對

判斷串t是不是串s的字串，s稱為目标串，t稱為模式串。

BF算法

概述

BF(Brute Force)，名字翻譯過來就是“簡單粗暴”，就是從s的第一個字元開始嘗試比對。如果比對失敗就從s的下一個字元開始（指針回溯）。這裡需要注意的是i=i-j+1的妙用，它能讓每次i都比j多1，進而實作“比對失敗就從s的下一個字元開始比對”。

BF代碼

typedef struct {
	char data[MaxSize];
	int Length;
}SqString;


int BF(SqString s, SqString t)
{
	int i = 0, j = 0;
	while (i < s.Length && j < t.Length)
	{
		if (s.data[i] == t.data[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;//妙極了
			j = 0;
		}
	}
	if (j >= t.Length)
	{
		return (i - t.Length);//易錯
	}
	else
		return -1;
}
           

測試：

#include "mystr.h"
#include <stdlib.h>
int main()
{
	int i = 0;
	SqString s, t;
	char s1[] = "hagikhgdkhsdkgfgdsgh";
	char s2[] = "sdk";
	printf("%d\n", StrAssign(s, s1));
	printf("%d\n",StrAssign(t, s2));

	printf("%d\n", BF(s,t));

	return 0;
}
           

性能

設s長為n，t長為m。

最好的情況下s的開頭與t正好比對，時間複雜度為O(m)。

最壞的情況下s的末尾才與t正好比對，時間複雜度為O(m×n)。

平均的時間複雜度為O(m×n)。