Untitled

 avatar
user_3907072
abc
2 years ago
3.8 kB
2
Indexable
Never
#include<bits/stdc++.h>
using namespace std;
#define n 6

struct XAU {
    char ten[100];
};

XAU d[n] = {
    "child there is",
    "one",
    "child",
    "in",
    "one family child",
    "at present"
};

int Min_CD(int left, int right, int mini) {
    if(left == right) {
        if(mini > strlen(d[left].ten)) {
            mini = strlen(d[left].ten);
        }
        return mini;
    }
    if(right - left == 1) {
        if(strlen(d[left].ten) < strlen(d[right].ten)) {
            if(mini > strlen(d[left].ten)) {
                mini = strlen(d[left].ten);
            }
        } else {
            if(mini > strlen(d[right].ten)) {
                mini = strlen(d[right].ten);
            }
        }
        return mini;
    }
    int m = (left + right) / 2;
    mini = Min_CD(left, m, mini);
    mini = Min_CD(m+1, right, mini);
    
    return mini;
}

int tong_CD(int left, int right) {
    if(left == right) {
        return strlen(d[left].ten);
    }

    int m = (left + right) / 2;
    return tong_CD(left, m) + tong_CD(m+1, right);
}

XAU *b = new XAU[n];

void mergeSort(int left, int right) {
    if(left < right) {
        int m = (left + right) / 2;
        mergeSort(left, m);
        mergeSort(m+1, right);
        for(int i = left; i <= m; i++) {
            strcpy(b[i].ten, d[i].ten);
        }
        for(int j = m+1; j <= right; j++) {
            strcpy(b[right + m + 1 - j].ten, d[j].ten);
        }

        int i = left, j = right;
        for(int k = left; k <= right; k++) {
            if(strcmp(b[i].ten, b[j].ten) < 0) {
                strcpy(d[k].ten, b[i].ten);
                i++;
            } else {
                strcpy(d[k].ten, b[j].ten);
                j--;
            }
        }
    }
}

int timViTri(int left, int right, char* st) {
    if(left <= right) {
        int m = (left + right) / 2;
        if(strcmp(d[m].ten, st) == 0) {
            return m;
        } else if(strcmp(d[m].ten, st) > 0) {
            return timViTri(left, m-1, st);
        } else if(strcmp(d[m].ten, st) < 0){
            return timViTri(m+1, right, st);
        }
    }
    return -1;
}

int *S = new int[n];

int boyer_Moore_Horspool(char* P) {
    int dem = 0;
    int spt = 0;
    while(spt < n) {
        S[spt] = 0;
        char* T = d[spt].ten;
        int i = strlen(P);
        int v = strlen(P);
        while(i <= strlen(P)) {
            int x = v - 1, j = i - 1;
            while(T[j] == P[x] && x > -1) {
                j--;
                x--;
            }
            if(x < 0) {
                dem++;
                S[spt] = 1;
                break;
            } else {
                int index = -1;
                for(int k = x - 1; k >= 0; k--) {
                    if(T[j] == P[k]) {
                        index = k;
                        i = i + x - index;
                        break;
                    }
                }
                if(index == -1) {
                    i = i + v;
                }
            }
        }
        spt++;
    }
    return dem;
}

int main() {
    int mini = Min_CD(0, n-1, strlen(d[0].ten));
    for(int i = 0; i < n; i++) {
        if(strlen(d[i].ten) == mini) {
            cout<<d[i].ten;
        }
    }
    cout<<endl;
    cout<<tong_CD(0, n-1)<<endl;
    mergeSort(0, n-1);
    for(int i = 0; i < n; i++) {
        cout<<d[i].ten<<"\t";
    }
    cout<<endl;
    cout<<"Vi tri xuat hien : "<<timViTri(0, n-1, "one")<<endl;
    cout<<"Tu nay xuat hien trong "<<boyer_Moore_Horspool("child")<<" xau"<<endl;
    for(int i = 0; i < n; i++) {
        // if(S[i] == 1) {
        //     cout<<d[i].ten<<"\t";
        // }
        cout<<S[i]<<" ";
    }
    cout<<endl;
}