UVa 156 反片语

62 阅读 0 评论 41 点赞

我是靠谱客的博主优美彩虹，最近开发中收集的这篇文章主要介绍UVa 156 反片语，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：题目是要找出ananagram。什么是ananagram？它是anagram的反面。anagram是什么呢？就是在给定字典中可以通过字母重排得到的字符串，而且忽略大小写。（因为看错了那两个单词，一直对ananagram的定义很困惑，因为一会儿感觉字母重排可得到的是，一会儿感觉字母重排不可得到的是，其实那是两个单词。）

思路：先对输入词典进行词典排序，构建每个词的对应的顺序单词（即每个词在原位置字母排序）,然后重头开始匹配就可以了。这里我是用an数组标记每一位是否“安全”，即是否需要输出。（刚开始没注意输出的要是原单词，然后就对sdic数组进行排序了，这样可以很快找出哪些词是ananagram、哪些是anagram，但是却和原字母对应不起来。因为感觉这样排序后、一个类似去重的过程进行处理，效率比较高，就一直沿着这个思路，甚至想着把是ananagram的词在原词典中搜索，但这样并不是原单词的字典序输出；可能可以继续改进下去，但有点麻烦，而且思路不清晰，绕来绕去的）

注意：有时候题目没看清，做下去不仅是错的，而且你会在这个错的基础上进行改进。但也许，你之前忽略了的微小的地方，反而在实现上有很大差别，那个错了的思路反而把你带得越来越远，把一个简单的题变麻烦了~（如果你是在那样的情况下改进的，而且发现那样改进下去绕来绕去太麻烦了，那你可以考虑，是不是那本身就是错误的思路，简单问题复杂化了，新建一个cpp重新写吧~）

Code：

//#define LOCAL
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
#define N 25
#define M 1010

int cmp_c(const void *_a,const void *_b);
int cmp_string(const void *_a,const void *_b);
void find(int n,int i);

char dic[M][N];//原单词词典 
char sdic[M][N];//各单词在原位置字母排序后的词典，且转小写 
//char sorted[M][N];//单词转小写且字母排序后，进行整个词典排序，即对sdic进行词典排序 
bool an[M];

int main()
{
 #ifdef LOCAL
  freopen("data156.in","r",stdin);
  freopen("data156.out","w",stdout);
 #endif 
    
 char temps[N];
 int n=0;
 while(scanf("%s",temps)&&temps[0]!='#')
 {
  strcpy(dic[n++],temps);//dic保存的是原输入单词 
 }//n正好为dic的行数0~n-1
 qsort(dic,n,sizeof(dic[0]),cmp_string);//对原单词词典排序，便于输出 
 
 for(int i=0;i<n;++i)
 {                                     
  int len=strlen(dic[i]);
  for(int j=0;j<len;++j)
   sdic[i][j]=tolower(dic[i][j]);
  sdic[i][len]='';
  qsort(sdic[i],strlen(sdic[i]),sizeof(char),cmp_c);
  //strcpy(sorted[i],sdic[i]);
 } 
 //qsort(sorted,n,sizeof(sorted[0]),cmp_string);  
 for(int i=0;i<n-1;++i)
 {
  find(n,i);       
 }
 
 for(int i=0;i<n;++i)
 {
  if(an[i]==0) 
   printf("%sn",dic[i]);       
 }
 return 0; 
} 

void find(int n,int i)
{
 for(int j=i+1;j<n;++j)
 {
  if(an[j]==0)//只检查不安全的位置 
   if(strcmp(sdic[i],sdic[j])==0)
   {
    an[i]=an[j]=1;                       
   }        
 }    
}

int cmp_string(const void *_a,const void *_b)
{
 char *a=(char*)_a;
 char *b=(char*)_b;
 return strcmp(a,b);   
}

int cmp_c(const void *_a,const void *_b)
{
 char *a=(char*)_a;
 char *b=(char*)_b;
 return *a-*b;   
}