NkOJ 2218 (사전 트 리 + STL)

2218: 음성 인식
Time Limit: 1000 ms   
Memory Limit: 65536 kB  
Total Submit : 74 
(18 users)   
Accepted Submit : 15 
(13 users)   
Page View : 318 
Font Style:
Aa
Aa
Aa
 
최근 몇 년 동안 음성 인식 기술 이 점점 유행 하고 있 습 니 다. 음성 인식 기술 이 정확 한 지 확인 하려 면 다음 과 같은 방법 을 사용 할 수 있 습 니 다. 첫 번 째 기계 가 소 리 를 내 어 단 어 를 읽 고 두 번 째 기 계 는 첫 번 째 소리 에 따라 음성 인식 과 발성 을 하 며 세 번 째 기 계 는 두 번 째 기계 가 내 는 소 리 를 받 고 소 리 를 낼 수 있 습 니 다. 이런 식 으로 마지막 기계 가 소 리 를 낼 때 까지 유추 할 수 있 습 니 다.
이 과정 에서 약간의 편차 가 생 길 수 있 기 때문에 기계 가 많 을 때 마지막 에 들 은 말 은 종종 초기 문장 과 큰 차이 가 있다.몇 차례 의 실험 을 거 친 후에 우 리 는 두 기계 사이 에서 전 달 될 때 어떤 단 어 는 종종 다른 특정한 단어 로 잘못 변 하고 어떤 단 어 는 변 하지 않 는 다 는 것 을 알 게 되 었 다.우 리 는 이미 이러한 단어 전환 목록 을 수집 하 였 습 니 다. 이 제 는 초기 문장 이 마지막 에 어떻게 될 지 알 고 싶 으 면 프로그램 을 써 서 실현 하 십시오.
Input
여러 그룹의 데 이 터 를 입력 하 십시오.
첫 줄 은 정수 T (1 & lt; = T & gt; = 100) 로 몇 개의 테스트 데이터 가 있 는 지 를 나타 낸다.
각 그룹의 데이터 첫 줄 은 두 개의 정수 N 과 M (2 & lt; = N & gt; = 100, 0 & gt; = M & gt; = 100) 을 포함 하여 각각 기계 의 수량 과 단어 전환 목록 의 길 이 를 나타 낸다.그 다음 에 M 줄 이 있 는데 줄 마다 두 개의 빈 칸 으로 구 분 된 단어 a 와 b 를 포함 하여 단어 a 가 전달 하 는 과정 에서 반드시 b 가 된다 는 것 을 나타 낸다.입력 데 이 터 는 중복 되 지 않 음 을 보증 합 니 다.마지막 줄 에는 하나의 빈 칸 으로 구 분 된 몇 개의 단 어 를 포함 하여 초기 문장 을 표시 하고 문장의 총 길 이 는 100 자 를 넘 지 않 습 니 다.같은 단어의 다른 시 태 는 다른 단어 로 여 겨 진다.
물론 앞에서 말 한 바 와 같이 목록 에 없 는 단 어 는 영원히 변 하지 않 는 다.
Output
각 그룹의 테스트 데이터 에 대해 "Case \ # c: s" 줄 을 단독으로 출력 합 니 다. (따옴표 포함 하지 않 음)그 중에서 c 는 테스트 데이터 번호 이 고 s 는 마지막 으로 우리 가 들 은 문장 이다.s 의 형식 은 입력 데이터 의 초기 문장 형식 과 같 습 니 다.
Sample Input

2
4 3
ship sheep
sinking thinking
thinking sinking
the ship is sinking
10 5
tidy tiny
tiger liar
tired tire
tire bear
liar bear
a tidy tiger is tired

Sample Output

Case #1: the sheep is thinking
Case #2: a tiny bear is bear

Source
'Crazy for Programming' Nankai University Programming Contest IX
Best User : cztianshi
제 가 먼저 사용 한 사전 나 무 는 지나 갈 수 없 었 습 니 다. 나중에 대 신의 모방 을 보 았 습 니 다. 완전히 베 낀 것 이 라 고 할 수 있 겠 죠? STL 로 바 꾸 어 최종 적 으로 해 결 했 습 니 다. 그런데 왜 사전 나무 가 틀 렸 는 지 모 르 겠 습 니 다. 다른 대소 문자 가 있 을 수도 있 습 니 다!

/*
    
#include
using namespace std;

struct Trie
{
    Trie * next[26];
 char new_word[100];
 bool flag;//          
}*root;/           

void insert(char *str1,char *str2)
{
    int len =strlen(str1);
    Trie *s = root;
    for (int i = 0; i < len; i++)
 {
  if (s->next[str1[i] - 'a'])
            s = s->next[str1[i] - 'a'];
        else
  {
            Trie* t = new Trie;
            memset(t, 0, sizeof (Trie));
            s->next[str1[i] - 'a'] = t;
            s = t;
        }
 }
 strcpy(s->new_word,str2);
 //cout<new_word<flag = 1;
}

int find(char *str)
{
    int len = strlen(str);
// cout<next[str[i] - 'a'])
            s = s->next[str[i] - 'a'];
        else
            return 0;
 }
 if(s->flag==1)
  strcpy(str,s->new_word);
 return s->flag;/flag          
}


void del(Trie *root)
{
    Trie *s = root;
    for (int i = 0; i < 26; i++)
 {
        if (s->next[i])
            del(s->next[i]);
    }
    delete s;
    s = NULL;
}


int main()
{
 int t,n,m,i,start,j,k,tag=0;
 char str1[100],str2[100],alticle[100],word[100],new_alticle[100][100];
 cin>>t;
 while(t--)
 {
  tag++;
  root=new Trie;
  memset(root,0,sizeof(Trie));
  cin>>n>>m;
  for(i=0;i>str1>>str2;
   insert(str1,str2);
  }
  getchar();
 // cout<
#include
#include
#include
#include