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