boyer moore

thuật toán boyer moore
mail@pastecode.io avatar
unknown
plain_text
2 years ago
748 B
7
Indexable
Never
int boyerMooreHorspool(string s, string p)
{
    int cnt = 0;
    int lenS = s.size(), lenP = p.size();
    int i = lenP;
    while(i <= lenS)
    {
        int x = lenP - 1, j = i - 1;
        while(s[j] == p[x] && x >= 0) {
            j--;
            x--;
        }
        if(x < 0) {
            cnt++;
            i += lenP;
        }
        else {
            int idx = -1;
            for(int q = x-1; q >= 0; q--) {
                if(s[j] == p[q]){
                    idx = q;
                    break;
                }
            }

            if(idx == -1){
                i += lenP;
            }
            else {
                i += x - idx;
            }
        }
    }
    return cnt;
}