Skip Letter Code
Romeo and Juliet are college students in the city of Verona and are in love with each other. Unfortunately, both their families are not very glad with this fact. They are trying to prevent any attempts of young people to communicate. Thus, Romeo and Juliet had to introduce their special code to be capable of writing love letters to each other. Both of them have a little book of Shakespeare sonnets and agreed to use this book as a dictionary for their code. The code is like follows: only words that appear in the dictionary may be used in the love letter. Then, the person who writes the letter may skip some letters in each word. Of course that person tries to skip as may letters as possible, but he would keep in mind that the letter should be decoded with just one possibility for each word. Oh, such a difficult task! Fortunately, both of the lovers have a personal computer and you can (can't you?) help them writing the program, that being given with the dictionary and the coded message decodes one if there is just one way to decode the message or reports that there could be more than one decoding possibility. Thus, you will help both writing and reading persons.
This problem contains multiple test cases!
The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.
The output format consists of N output blocks. There is a blank line between output blocks.
Input
First line of the input contains single integer 1 <= N <= 100 - number of words in a dictionary. Next N lines each contain one word from the dictionary. Each word in a dictionary is not longer than 5 characters and (as well as coded message) consists from capital letters A to Z. The rest of file (up to # character) contains coded message (no longer than 10^6 characters) which is coded words separated by space(s) and/or newline characters.
Output
Output should contain single line with word AMBIGUITY if there could be more than one possible decoding of the message or decoded message with all spaces and newline characters kept intact. Note, that # character should not be printed.
Sample Input
2
3 I LOVE YOU I E U#
3 I LOVE YOU I O Y#
Sample Output
I LOVE YOU
AMBIGUITY
이 문제는 연속된 문자열을 디코딩해야 합니다. 연속적이며, 순서가 있습니다. 만약 인코딩에
여러 개의 답안이 있으면 AMBIGUITY를 출력하기 때문에 매핑이 유일한 것이어야 합니다. 조합으로 인코딩된 모든 가능성을 열거할 수 있습니다.
자, 그리고 맵 저장 위치를 사용하세요. 그러면 뒤에 조회만 하면 됩니다.
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <iostream>
using namespace std;
map < string, int > vis;
const int N = 105, maxn = 1000005;
char word[N][N], op[N], ans[maxn];
int s, len;
void dfs ( int k, string str, int n, int pos )
{
if ( k > n || len-pos < n-k ) //
return ;
if ( k == n )
{
if ( vis[str] == 0 || vis[str] == s )
//
vis[str] = s;
else // -1
vis[str] = -1;
return ;
}
for ( int i = pos; i < len; i ++ ) // i+1
dfs ( k+1, str+word[s][i], n, i+1 );
}
int is_letter ( char ch )
{
return ch >= 'A' && ch <= 'Z' || ch >= 'a' && ch <= 'z';
}
int main ( )
{
int T, n, tag, cnt;
//freopen ( "in0.in", "r", stdin );
scanf ( "%d", &T );
string str;
while ( T -- )
{
tag = 0;
vis.clear ( );
scanf ( "%d", &n );
for ( int i = 1; i <= n; i ++ )
scanf ( "%s", word[i] );
for ( int i = 1; i <= n; i ++ )
{
str = "";
len = strlen ( word[i] );
for ( int j = 1; j <= len; j ++ ) //
{
s = i;
dfs ( 0, str, j, 0 );
}
}
getchar ( );
strcpy ( ans, "" );
cnt = 0;
while ( gets ( op ) )
{
int size = strlen ( op );
if ( tag )
{
if ( op[size-1] == '#' )
break ;
continue ;
}
for ( int i = 0; i < size; i ++ )
{
string ch = "";
if ( is_letter ( op[i] ) )
{
while ( is_letter ( op[i] ) )
{
ch = ch+op[i];
i ++;
}
i --;
if ( vis[ch] == -1 || vis[ch] == 0 )
tag = 1;
else
{ int pos = vis[ch];
int l = strlen ( word[pos] );
for ( int i = 0; i < l; i ++ )
ans[cnt ++] = word[pos][i];
}
}
else if ( op[i] != '#' )
ans[cnt ++] = op[i];
}
ans[cnt ++] = '
'; //
ans[cnt] = '\0';
if ( op[size-1] == '#' )
break ;
}
printf ( "%s", tag ? "AMBIGUITY
" : ans );
if ( T ) //
printf ( "
" );
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.