Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1891
In his endless attempt to keep his secret documents safe, Bob has designed yet another coding system. In this system, every character is replaced by a unique positive integer value – which we call the code for a character. However, this system – as expected – is not the best in the world. So more than one plain text can result in the same encrypted string. Here are a few more notes: • The document consists exclusively of lower-case letters. • The code for a letter is no more than 99. • The encrypted string does not contain more than 100 characters. • A code may or may not be preceded by a 0 in the encrypted string (note the 2nd sample test case). Given the codes for each character and the encrypted string, you have to find all the plain text strings in alphabetical order that produces that encrypted string. Input There will be no more than 500 test cases. Each test case starts with an integer N, which gives the number of unique characters in the document. Each of next N lines contains a character in the letter and its code. The last line in the test case gives the encrypted string. The last test case will have N = 0. This last test case need not be processed. Output For each test case, print the test case number and the possible plain texts for the given encrypted string. If there is more than 100 possible strings report only the first 100 strings. Print a blank line after the output for each test case.
Sample Input 5 a 12 b 1 c 2 d 3 e 23 123 2 o 10 x 1 1010101 0
Sample Output Case #1 ad bcd be Case #2 ooox ooxx oxox oxxx xoox xoxx xxox xxxx
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int cnt;
void dfs(int idx,string& cur,vector < pair idx++;
if(idx>=t.length()) return;
for(auto& p : encode){
if(p.second.length() > t.length()-idx) continue;
bool valid = true;
for(int i=0;i<p.second.length() && valid;i++){
if(t[i+idx] != p.second[i]) valid = false;
}
if(valid){
cur += p.first;
dfs(idx+p.second.length(),cur,encode,t);
cur.pop_back(>;
}
if(cnt>= 100) return;
}
}
int main()
{
int n,v,tc=1;
char c;
string t;
while(cin>>n,n){
string cur = "";
vector<pair < char,string>> encode;
for(int i=0;i < n;i++){
cin >> c >> v;
encode.push_back({c,to_string(v)});
}
cin >> t;
sort(encode.begin(),encode.end());
cnt = 0;
printf("Case #%d\n",tc++);
dfs(0,cur,encode,t>;
cout << endl;
}
}
Input
a 12
b 1
c 2
d 3
e 23
123
2
o 10
x 1
1010101
0
Output
ad
bcd
be
Case #2
ooox
ooxx
oxox
oxxx
xoox
xoxx
xxox
xxxx
Demonstration
UVA Online Judge solution - 10950-Bad Code - UVA Online Judge solution in C,C++,java