|
auto cal(size_t sz)->decltype(auto)
{
decltype(sz) k = 0;
decltype(sz) cur = 1;
while (cur - 1 < sz + k )
{
cur <<= 1;
k++;
}
return k;
}
复制代码
复制代码
bool encode(const string &s, string &d)
{
d.clear();
auto k = cal(s.size());
d.resize(s.size() + k);
for (decltype(d.size()) i = 0, j = 0, p = 0; i!= d.size();i++)
{
if ((i + 1) == pow(2,p) && p < k)
{
d[i] = '0';
p++;
}
else if (s[j] == '0' || s[j] == '1')
d[i] = s[j++];
else
return false;
}
for (auto i = 0; i != k;i++)
{
int count = 0 ,index = 1 << i;
for (auto j = index - 1; j < d.size() ;j += index)
for (auto k = 0; k!= index && j < d.size(); k++, j++)
count ^= d[j] - '0';
d[index - 1] = '0' + count;
}
return true;
}
复制代码
解码与校验:
复制代码
auto antiCal(size_t sz)->decltype(auto)
{
decltype(sz) k = 0;
decltype(sz) cur = 1;
while (cur < sz)
{
cur <<= 1;
k++;
}
return k;
}
auto decode(string &s, string &d)->decltype(auto)
{
s.clear();
auto k = antiCal(d.size());
s.resize(d.size() - k);
decltype(d.size()) sum = 0;
for (decltype(k) p = 0;p != k;p++)
{
int pAnti = 0;
decltype(k) index = 1 << p;
for (decltype(d.size()) i = index - 1;i < d.size(); i+=index)
{
for (auto j = 0; j < index && i < d.size(); i++, j++)
pAnti ^= d[i] - '0';
}
sum += pAnti << p;
}
if (sum != 0)
d[sum - 1] = (1- (int)(d[sum - 1] - '0')) + '0';
for (decltype(d.size()) i = 0, p = 0,j = 0; i != d.size(); i++)
{
if ((i + 1) == (1 << p) && p < k)
p++;
else
s[j++] = d[i];
}
return sum;
}
复制代码
测试样例:
复制代码
int main()
{
string source, dest;
while (cin >> source)
{
if (encode(source,dest))
{
cout << "Source: " <<source << endl;
cout << "Dest: " << dest << endl;
}
size_t index;
cout << "----input error index : ";
cin >> index;
auto k = dest.size();
if (index != 0 && index <= dest.size())
dest[index - 1] = (1 - (int)(dest[index - 1] - '0')) + '0';
cout << "Code " << dest <<endl;
auto ret = decode(source,dest);
if (ret == 0)
{
cout << "Source: " <<source << endl;
cout << "Dest: " <<dest << endl;
}
else
{
cout << "Error index "<< ret << endl;
cout << "Corret source: " <<source << endl;
cout << "Corret dest: " <<dest << endl;
}
cout << endl;
}
return 0;
}
10101
Source: 10101
Dest: 001101011
----input error index : 8
Code 001101001
Error index 8
Corret source: 10101
Corret dest: 001101011
1001010101010101010111111001101
Source: 1001010101010101010111111001101
Dest: 1111001101010100101010101111110101101
----input error index : 20
Code 1111001101010100101110101111110101101
Error index 20
Corret source: 1001010101010101010111111001101
Corret dest: 1111001101010100101010101111110101101
1
Source: 1
Dest: 111
----input error index : 0
Code 111
Source: 1
Dest: 111 |
|