海明碼檢驗和糾錯

/*
   海明碼檢驗與糾錯.
*/
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
/*
    測試樣例
    110010100000
    0011101
    1110110
    011001011001
    0001001

*/

char s[105];  // 用來接收資訊位字元串
char ans[1005]; //得出的海明碼存儲在這裡
const int hehe[] = {1,2,4,8,16,32,64,128,256,512,1024}; //這個辦法真是呵呵了。。。。
const int hehe_len = sizeof(hehe) / sizeof(int); //呵呵數組的長度，懶得算
int r_len;        //校驗位的位數
int k; //資訊位個數
int step; //在海明碼中資訊位的最高下标。
int s1[105];
int s1_len;
struct Node
{
    int a[10];  //存儲ri是由誰生成的（存下标）
    int len ;  //a數組的長度
    int val;  //校驗位的值
} r[105];
int pow(int b,int r_len) //幂運算
{
    int ret = 1;
    for(int i = 1; i <= r_len; ++i)
        ret *= b;
    return ret;
}
bool findPos(int n)  //找到hehe中的數

{
    for(int i = 0; i < hehe_len; ++i)
        if(hehe[i] == n)
            return true;
    return false;
}
int f(char c)  //char -> int

{
    return c - '0';
}

int zh()

{
    int ret = 0;
    for(int i = 0;i < r_len;++i)
        if(s1[i])
           ret += pow(2,i);
    return ret;
}
void solve()

{
    int len_n = strlen(s + 1);
    for(k = len_n;k >= 0;--k)
        if(pow(2,len_n - k) >= len_n + 1)
           {
         r_len = len_n - k;
         break;
        }


    memset(ans,-1,sizeof ans);
    memset(r,0,sizeof r);

    for(int i = 1,j = len_n; i <= j; ++i,--j) //逆序字元串,以便對應I1,I2....
    {
        char t = s[i];
        s[i] = s[j];
        s[j] = t;
    }
    //printf("%s\n",s);
    r_len = 0;
    for(int i = 1;i <= len_n;++i)
    {
        if(findPos(i))
        {
            r[r_len++].val = f(s[i]);
        }
    }
    int i;
    for(step = 3,i = 1;i <= len_n;)
    {
        if(!findPos(step))
        {
            if(findPos(i))++i;
            else ans[step++] = s[i++];
        }
        else step++;
    }

    //printf("step = %d\n",step);
    for(int j = step - 1; j >= 3; --j)   // 找出ri是由哪幾位在一起生成的.
    {
        if(!findPos(j))
        {
            int t = j;
            for(int l = hehe_len - 1; l >= 0 && t > 0; --l)
            {
                if(t >= hehe[l])
                {
                    t -= hehe[l];
                    r[l].a[r[l].len++] = j;
                }
            }
        }
    }
    for(int i = 1,j = 0;i <= max(step - 1,pow(2,r_len - 1));++i)
    {
        if(findPos(i))
        {
            ans[i] = r[j++].val + '0';
        }
    }
    s1_len = 0;
    for(int i = 0;i < r_len;++i)
    {
        s1[i] = r[i].val;
        for(int j = 0;j < r[i].len;++j)
        {
            s1[i] = s1[i] ^ f(ans[r[i].a[j]]);
        }
    }
    int pos = zh();
    if(pos == 0)
    {
        printf("這個海明碼沒有錯誤！\n");
    }
    else
    {
        ans[pos] == '0' ? ans[pos] = '1' : ans[pos] = '0';
        printf("第%d位出現錯誤,改正後如下\n",pos);
        for(int i = max(step - 1,pow(2,r_len - 1));i >= 1 ;--i)
            printf("%c",ans[i]);
        printf("\n");
    }

}
int main(){
    while(~scanf("%s",s + 1)) solve();
    return 0;
}