基于鄧俊輝老師的c++數(shù)據(jù)結(jié)構(gòu)
問(wèn)題描述：
給定文本串T,長(zhǎng)度n 如：1001101101
模式串P,長(zhǎng)度m，如： 1011
此時(shí)默認(rèn)的字符集是{'1','0'}
求成功匹配的字符首位置
算法描述：
將P和T從頭對(duì)齊，依次比對(duì)。一旦失敗，將P右移一位，繼續(xù)從頭比對(duì)。
蠻力算法
而代碼實(shí)現(xiàn)上則是由兩個(gè)指針i,j分別指向T，P
代碼實(shí)現(xiàn)：
//p:pattern模式串 T:text文本串
int match1(char* P,char* T)
{
size_t n = strlen(T),i=0;//獲得文本串的長(zhǎng)度，設(shè)定指向文本串的指針i
size_t m = strlen(P),j=0;//獲得模式串的長(zhǎng)度，設(shè)定指向模式串的指針j
while(j<m && i<n)
{
if(T[i]==P[j])//成功匹配字符則同時(shí)向右挪一位
{
i++;
j++;
}
else{
i-=(j-1);//相當(dāng)于i先減去j再加1，也就是在原來(lái)的位置上右移一位
j=0;//j重新歸零
}
}
return i-j;//返回成功匹配的起始位置
}
復(fù)雜度分析：
從最壞情況分析，比如：
T：0000000000000000000000000000001
P : 0001
那么需要比較n-m+1輪，每輪m次 比對(duì)
當(dāng)n>>m時(shí)，漸進(jìn)時(shí)間復(fù)雜度是O(n*m)
但事實(shí)并不悲觀。
實(shí)際上，當(dāng)前字符集的個(gè)數(shù)僅僅為2，極其容易出現(xiàn)局部匹配。
假如字符集的數(shù)目很可觀，那么將很難出現(xiàn)局部匹配，此時(shí)m->1
時(shí)間復(fù)雜度趨近于O(n)
