最小サブストリング検索

テーマ:1つの文字列s 1と1つの小さい列s 2をあげて、アルゴリズムを求めてs 1の中でs 2の中のすべての文字を含む最も小さい子の列を見つけることができます.例えば,s 1="ADOBECODEBANC"s 2="ABC"の最小子列は"BANC"であり,O(N)のアルゴリズムが要求される.
解析:2つのポインタp 1,p 2を設定し、s 1列の先頭を初期化します.p 1,p 2ポインタ間のs 1サブストリング文字がs 2のすべての文字を含む場合、p 1++は、2つのポインタ間のサブがs 2のすべての文字を完全に含まない場合、p 2++(ポインタ間隔を大きくする)は、サブストリングを合法的に含む最小ストリングの開始位置を記録する.上記の伸縮を行う場合、s 2列の含有状況をどのように迅速に記録しますか?hashテーブルを使用して、文字の出現回数を記録し、p 1++の場合、対応するアルファベットのカウントを1に減らし、p 2++の場合、対応するアルファベットのカウントを1に加算します.

int FindMinSubString(char* s1, char* s2)  
{  

    int hash_table[256];  

    /* 
            hash  ,s2         0, 
                
    */  
    for (int i=0; i<256; i++)  
    {  
        hash_table[i] = -1;  
    }  

    for (char* p = s2; *p != '\0'; p++)  
    {  
        hash_table[*p] = 0;  
    }  

    char* p1 = s1;  
    char* p2 = s1;  

    //      
    int min_len = 2100000000;  

    //          
    char* min_p1 = s1;  
    char* min_p2 = s1;  

    //  p1 p2           ,count == s2_len   s2  
    int count = 0;  

    int s2_len = strlen(s2);  

    /* 
          p2  s1      ，     
              ，    s2 
    */  
    while(*p2 !='\0' || s2_len==count)  
    {  

        //p1...p2   s2  
        if (count//  s2        
            if (hash_table[*p2] == 0)  
            {  
                count++;  
                hash_table[*p2]++;  
            }  
            else if (hash_table[*p2] > 0)  
            {  
                hash_table[*p2]++;  
            }  

            p2++;  
        }  

        //   else       if    count++;  
        if(count == s2_len)  
        {  
            if (p2-p1 < min_len)  
            {  
                min_p1 = p1;  
                min_p2 = p2;  
                min_len = p2-p1;  
            }  

            //    
            hash_table[*p1]--;  
            if (hash_table[*p1] == 0)  
            {  
                count--;  
            }  
            p1++;  
        }  
    }  

    //    
    while(min_p1 < min_p2)  
    {  
        printf("%c",*min_p1);  
        min_p1++;  
    }  

    return min_len;  
}