Cryptcowgraphy
Brian Dean
The cows of Farmer Brown and Farmer John are planning a coordinated escape from their respective farms and have devised a method of encryption to protect their written communications.
Specifically, if one cow has a message, say, "International Olympiad in Informatics", it is altered by inserting the letters C, O, and W, in random location in the message, such that C appears before O, which appears before W. Then the cows take the part of the message between C and O, and the part between O and W, and swap them. Here are two examples:
International Olympiad in Informatics
->
CnOIWternational Olympiad in Informatics
International Olympiad in Informatics
->
International Cin InformaticsOOlympiad W
To make matters more difficult, the cows can apply their encryption scheme several times, by again encrypting the string that results from the previous encryption. One night, Farmer John's cows receive such a multiply-encrypted message. Write a program to compute whether or not the non-encrypted original message could have been the string:
Begin the Escape execution at the Break of Dawn
PROGRAM NAME: cryptcow
INPUT FORMAT
A single line (with both upper and lower case) with no more than 75 characters that represents the encrypted message.
SAMPLE INPUT (file cryptcow.in)
Begin the EscCution at the BreOape execWak of Dawn
OUTPUT FORMAT
Two integers on a single line. The first integer is 1 if the message decodes as an escape message; 0 otherwise. The second integer specifies the number of encryptions that were applied (or 0 if the first integer was 0).
SAMPLE OUTPUT (file cryptcow.out)
1 1
----------------------------------------------------
解法dfs+elfhash。
基本原理就是暴搜，但是要加上减枝。
以下减枝：
1. 由于添加的COW是一起的，因此给出的字符串的字符个数应该等于47（目标字符串的长度）+3*k。如果不满足就可直接判断无解。
2. 除了COW三个字符外，其他的字符的个数应该和目标串相一致。如果不一致也可直接判断无解。
搜索中间肯定会出现很多相同的情况，因此需要开一个hash来记录搜索到过哪些字符串，每搜索到一个字符串，就判重。
如果重复直接剪枝。这里的字符串的hash函数可以采用ELFhash，但由于ELFhash的数值太大，
所以用函数值对一个大质数（我用的是35023）取余，这样可以避免hash开得太大，同时又可以减少冲突。
实验证明，加上elfhash之后，最复杂的情况用时也只有0.243.
3. 对搜索到的字符串，设不包含COW的最长前缀为n前缀（同样也可以定义n后缀），那么如果n前缀不等于目标串的长度相同的前缀，
那么当前字符串一定无解，剪枝。N后缀也可采取相同的判断方法。
4. 一个有解的字符串中，COW三个字母最早出现的应该是C，最后出现的应该是W，如果不满足则剪枝。
5 . 当前字符串中任意两个相邻的COW字母中间所夹的字符串一定在目标串中出现过。如果不符合可立即剪枝。
6. 首先枚举o的位置，那么c的位置已经在0和O之间了，w的位置已经在o之后。
7. 在判断当前串的子串是否包含在目标串中的时候，可以先做一个预处理：记录每一个字母曾经出现过的位置，然后可以直接枚举子串的第一个字母的位置。这样比用pos要快2倍左右。
8. 判断某个字符是否在原始串中。给每一个字符计算一个hash值，为其上一个字符左移n位加上当前字符的值。这样就很容易个判断是否含有这个字符串了
------------------------------------------
/*
ID:yunleis2
PROG:cryptcow
LANG:C++
*/
#include<iostream>
#include<fstream>
#include<string.h>
#include<ctime>
using namespace std;
char origin[]="Begin the Escape execution at the Break of Dawn";
int hashvalue[60];
#define HASHSIZE 871
int hashpos[3][HASHSIZE];
char encode[80];
int cnum,onum,wnum;
long begintime;
#define isencodechar(ch) (ch=='C'||ch=='O'||ch=='W')
int length;
int orilen;
#define MAXHASH 35023
bool hashsearch[MAXHASH];
inline bool exists(char enc[],int begin,int end){
for(int i=begin+1;i<=end;i++){
int hashvalue=enc[i-1]<<5;
hashvalue+=enc[i];
hashvalue%=HASHSIZE;
bool flag=false;
for(int j=0;j<3;j++){
int pos=hashpos[j][hashvalue];
if(pos==-1)
break;
if(pos!=-1&&origin[pos]==enc[i])
flag=true;
}
if(!flag)
return false;
}
return true;
}
fstream fin("cryptcow.in",ios::in );
fstream fout("cryptcow.out",ios::out);
void search(char * encode,int depth);
int main()
{
fin.getline(encode,80);
cout<<encode<<endl;
//check header;
cnum=onum=wnum=0;
for(int i=0;i<3*HASHSIZE;i++){
hashpos[i/HASHSIZE][i%HASHSIZE]=-1;
}
char value[70];
length=strlen(encode);
orilen=strlen(origin);
for(int i=0;i<length;i++){
if(encode[i]=='C')
++cnum;
if(encode[i]=='O')
++onum;
if(encode[i]=='W')
++wnum;
if(!isencodechar(encode[i])){
if(encode[i]==' ')
encode[i]=91;
encode[i]-=64;
}
if(i<orilen){
if(origin[i]==' ')
origin[i]=91;
origin[i]-=64;
int value=0;
if(i!=0){
value=origin[i-1]<<5;
}
value+=origin[i];
hashvalue[i]=value;
value%=HASHSIZE;
if(hashpos[0][value]==-1)
hashpos[0][value]=i;
else if(hashpos[1][value]==-1)
hashpos[1][value]=i;
else if(hashpos[2][value]==-1)
hashpos[2][value]=i;
else
cout<<"error"<<value<<" "<<i;
}
}
if((length-orilen)%3!=0){
fout<<0<<" "<<0<<endl;
return 0;
}
int last=-1;
for(int i=0;i<length;i++){
if(encode[i]=='C')
{
last=i;
}
if(encode[i]=='O')
{
if(!exists(encode,last+1,i-1)){
fout<<0<<" "<<0<<endl;
return 0;
}
last=i;
}
if(encode[i]=='W')
{
if(!exists(encode,last+1,i-1)){
fout<<0<<" "<<0<<endl;
return 0;
}
last=i;
}
}
if(cnum!=onum||cnum!=wnum){
fout<<0<<" "<<0<<endl;
return 0;
}
bool flag=true;
for(int i=0;i<length&&i<orilen;i++){
if(encode[i]=='C')
break;
else if(encode[i]!=origin[i])
{
fout<<0<<" "<<0<<endl;
return 0;
}
}
for(int i=0;i<length&&i<orilen;i++){
if(encode[length-i-1]=='W')
break;
else if(encode[length-i-1]!=origin[orilen-i-1]){
fout<<0<<" "<<0<<endl;
return 0;
}
}
#if 0
for(int i=0;i<length;i++){
cout<<(int)encode[i]<<" ";
}
cout<<endl;
for(int i=0;i<orilen;i++){
cout<<(int)origin[i]<<" ";
}
cout<<endl;
for(int i=0;i<orilen;i++){
cout<<hashvalue[i]<<" ";
}
#endif
begintime=clock();
search(encode,cnum);
fout<<0<<" "<<0<<endl;
//system("pause");
}
unsigned long
elf_hash( char *name)
{
unsigned long h = 0, g;
while (*name) {
h = (h << 4) + *name++;
if (g = h & 0xf0000000)
h ^= g >> 24;
h &= ~g;
}
return h;
}
void search(char * encode,int depth){
//cout<<<<endl;
long hash =elf_hash(encode)%MAXHASH;
if(hashsearch[hash])
{
cout<<encode<<endl;
return;
}
hashsearch[hash]=true;
char tmp[3];
char *decode=new char[strlen(encode)+1];
if(depth==0){
#if 0
for(int i=0;i<strlen(encode);i++){
if(encode[i]<65)
cout<<(char)(encode[i]+64);
else
cout<<encode[i];
}
cout<<endl;
#endif
if(exists(encode,0,strlen(encode)-1))
{
fout<<1<<" "<<cnum<<endl;
long end=clock();
cout<<end-begintime<<endl;
//system("pause");
exit(0);
}
}
if((strlen(encode)-orilen)%3!=0){
return ;
}
int cpos=-1,opos=-1,wpos=-1;
for(int j=0;j<strlen(encode);j++){
if(encode[j]=='O'){
opos=j;
for(int i=0;i<opos;i++){
if(encode[i]=='C'){
cpos=i;
bool flag=true;
if(cpos>opos)
continue;
if(cpos>0&&!isencodechar(encode[cpos-1])&&!(isencodechar(encode[opos+1]))){
tmp[0]=encode[cpos-1];
tmp[1]=encode[opos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
for(int s=strlen(encode)-1;s>opos;s--){
if(encode[s]=='W'){
wpos=s;
if((cpos<opos&&opos<wpos)){
bool flag=true;
if(cpos>0&&!isencodechar(encode[wpos-1])&&!(isencodechar(encode[cpos+1]))){
tmp[0]=encode[wpos-1];
tmp[1]=encode[cpos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
if(cpos>0&&!isencodechar(encode[opos-1])&&!(isencodechar(encode[wpos+1]))){
tmp[0]=encode[opos-1];
tmp[1]=encode[wpos+1];
tmp[2]=0;
flag=exists(tmp,0,1);
if(!flag)
continue;
}
int ptr=0;
//cout<<cpos<<" "<<opos<<" "<<wpos<<"\t";
for(int f=0;f<cpos;f++){
decode[ptr++]=encode[f];
}
for(int f=opos+1;f<wpos;f++)
decode[ptr++]=encode[f];
for(int f=cpos+1;f<opos;f++)
decode[ptr++]=encode[f];
for(int f=wpos+1;f<strlen(encode);f++)
decode[ptr++]=encode[f];
decode[ptr]=0;
search(decode,depth-1);
}
}
}
}
}
}
}
delete []decode;
}
Test 1: TEST OK [0.000 secs, 3076 KB]
Test 2: TEST OK [0.000 secs, 3076 KB]
Test 3: TEST OK [0.000 secs, 3076 KB]
Test 4: TEST OK [0.000 secs, 3076 KB]
Test 5: TEST OK [0.000 secs, 3076 KB]
Test 6: TEST OK [0.081 secs, 3076 KB]
Test 7: TEST OK [0.000 secs, 3076 KB]
Test 8: TEST OK [0.054 secs, 3076 KB]
Test 9: TEST OK [0.243 secs, 3076 KB]
Test 10: TEST OK [0.243 secs, 3076 KB]
![洛谷P2871-[USACO07DEC]Charm Bracelet S（01背包模板题）](https://ucc.alicdn.com/images/user-upload-01/20200725131735571.png?x-oss-process=image/resize,h_160,m_lfit)