/*

*子串查找(BF)

*BF算法是带回溯的模式匹配算法，如果缓冲标记已做的匹配，减少回溯，可以提高时间效率，当然会牺牲空间，实际运用中需要做权衡考虑

*主串MS,长度为N *子串ms,长度为n,n<=N *初始认为MS的[0，N-n]与子串是匹配位置，将其加入一个记录数组中，匹配个数为N-n+1 *将这些位置的字符与与子串第一个字符比较，匹配的位置前移存储，并记录匹配个数 *继续子串的其他字符进行比较，记录匹配的位置及匹配个数 *返回匹配个数 */ #include <string.h> #include <iostream> int getSubPos(int *rec,char *MS,int N,char *ms,int n) {     if(rec==NULL||MS==NULL||ms==NULL||n>N){         return 0;     }     int size=N-n+1;     for(int i=0;i<size;i++){         rec[i]=i;     }     for(int i=0; i<n;i++){         int psize=0;         for(int j=0;j<size;j++){             if(ms[i]==MS[rec[j]+i]){                 rec[psize++]=rec[j];             }         }         size = psize;     }     return size; }; int main(int argc,char **argv) {     char MS[32]="aaaaaabab";     char ms[12]="aab";     //char MS[32]="abdabcabbabcabceabcabc";     //char ms[12]="abcabc";     int rec[32]={0};     int size = getSubPos(rec,MS,strlen(MS),ms,strlen(ms));     for(int i=0; i<size; i++){         printf("find sub[%d]\n",rec[i]);     }     return 0; };