/*

*子串查找(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;
};