字元串比對—樸素模式比對

基本思想

把模式與目标逐一進行比較（首位置開始），直到碰到不比對的字元為止（模式右移一位再次開始比對）

算法可在第一個比對或是目标的結束處停止

算法過程

設T= T0T1, T2, …,Tn，P = p1, p2, …, pm

j為指向T中字元的下标指針，i為指向P中字元的下标指針

比對成功 (p1 = Tj , p2 = Tj+1 , …,  pm = Tj+m-1 )

 即，substr(T, j, m)

比對失敗  (pi ≠ Tj) 時，将P右移再行比較

嘗試所有的可能情況

效率分析

假定目标T的長度為n，模式P長度為m，且 m ≤ n 。在最壞的情況下，每一次循環都不成功，則一共要進行比較（n-m+1）次。每一次“相同比對”比較所耗費的時間，是P和T逐個字元比較的時間，最壞情況下，共m次。

是以，整個算法的最壞時間開銷估計為O(mn)

樸素算法的問題：回溯

樸素算法之是以效率不高的原因在于比對過程中目标串有回溯，且這些回溯并非必要

e.g.,

由1）可知： P5 ≠ T5， P0=T0, P1 = T1,同時由 P0 ≠P1可得知P0≠T1  故将 P 右移一位後第2）趟比較一定不等;  比較備援

那麼把P右移幾位合适？ 既能消除備援比較又保證不丢失配串呢？

代碼實作

int NaiveStrMatching(string T, string P) {

    int i=0; //模式的下标變量

    int j=0; //目标的下标變量

    int plen = p.length();  //模式的長度

    int tlen= T.length(); //目标的長度

    if(tLen < plen) //如果目标比橫式煙，比對無法成功

        return (-1);

    while(i<tlen){  //反複比較對應字元來開始比對

        if (T[j +i]==P[j+1]) {

            i++;

        }else{ //比對失敗，還8,門下移一位。

            i =0;

            j++;

            break;

        }

    }

    if(i>=pLen){

        return (j - pLen+1);

    } else {

        return (-1);

    }

}