思路：题目是先给出一系列要忽略的词（感觉像中文分词时候的去除停用词），然后在一系列titles中找keyword并排序输出。这里排序首先是按关键字的字母序，如果两个title有相同关键字，就按输入时title先出现的顺序；如果一个title里出现同一个词多次，就按该词在该title里的先后顺序输出。所以可以把keyword定义为一个结构体，然后给结构体排序，给结构体的排序用到的是qsort么，而qsort是不稳定排序，所以需要自己定义上述三个级别的排序（keyword字母序，title出现序，title中keyword出现序）。关键词排序完之后，按关键词输出即可（首先找关键词的h，即关键词所在title的行数，即可输出该title，输出到该关键词时，即到位置 关键词.ls 时，转大写，其他地方继续原文输出）。
这里我用的三维数据存的，第一维是行，即第几个title；第二维是word，即每个title的words；第三维就是具体的每个word字符串了。其中又用到了wordn数据来存第i个title有几个words。所以wordn的维数应预定义和title的行数相同，即TN。
注意：感觉不是很难，思路很清晰，就是给结构体排序，之前有个题的时候就想到用结构体排序了。但调了很长时间，主要是自己在写的时候发现问题，在增加wordn数组来保存每行title有多少个words时，把它的长度用成了WN而不是TN，结构WA了。（我觉得这个应该是RE才对啊，发现这个错误也是因为从网上找到一个很大的测试数据，跑有误，再增加一行，程序竟然崩，才发现的。不知道为什么为判WA啊，觉得是RE。还有就是UVa 老是挂，当时写完没及时交掉，交的时候已经过了段时间了，结果WA了，没刚写完就调程序效果好，这是UVa非常不好的地方，老是挂，老是不能及时交，总是一个题做完好过段时间重新调，虐人~） 这个地方也是挂自己，写的时候应该细心，不要抱着侥幸心理：如果交了过了就没问题，WA了再找。（结果没能及时交，等过了段时间回头调，印象就不深了，而且没有耐心一点一点从头检查，不然这个错误还是可以发现的）
这里是网上一测试数据：
Sample Input:
the
for
on
in
and
is
it
american
canadian
great
lakes
::
The Niagara Falls are voluminous waterfalls on the Niagara River
straddling the international border between the Canadian province
of Ontario and the U S state of New York The falls are
N miles BBBBBBSSSM kmBBBBBBSSS north northwest of Buffalo New York and
S miles BBBBBBSSSZ kmBBBBBBSSS south southeast of Toronto Ontario
between the twin cities of Niagara Falls Ontario
and Niagara Falls New York Niagara Falls is composed
of two major sections separated by Goat Island:
Horseshoe Falls the majority of which lies on the
Canadian side of the border and American Falls on the
American side The smaller Bridal Veil Falls are also
located on the American side separated from the main falls
by Luna Island Niagara Falls were formed when glaciers
receded at the end of the Wisconsin glaciation BBBBBBSSSthe last ice ageBBBBBBSSS
and water from the newly formed Great Lakes carved a path through
the Niagara Escarpment en route to the Atlantic Ocean
While not exceptionally high the Niagara Falls are very wide
More than six million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS of water falls
over the crest line every minute in high flow and almost
F million cubic feet BBBBBBSSSXYZKLM mSBBBBBBSSS on average It is the most
powerful waterfall in North America
The Niagara Falls are renowned both for their beauty and
as a valuable source of hydroelectric power Managing the
balance between recreational commercial and industrial uses
has been a challenge for the stewards of the falls since the TKLMs
Sample Output:
and water from the newly formed great lakes carved A path through
as A valuable source of hydroelectric power managing the
has been A challenge for the stewards of the falls since the tklms
receded at the end of the wisconsin glaciation bbbbbbsssthe last ice AGEBBBBBBSSS
over the crest line every minute in high flow and ALMOST
american side the smaller bridal veil falls are ALSO
powerful waterfall in north AMERICA
the niagara falls ARE voluminous waterfalls on the niagara river
of ontario and the u s state of new york the falls ARE
american side the smaller bridal veil falls ARE also
while not exceptionally high the niagara falls ARE very wide
the niagara falls ARE renowned both for their beauty and
AS a valuable source of hydroelectric power managing the
receded AT the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara escarpment en route to the ATLANTIC ocean
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on AVERAGE it is the most
BALANCE between recreational commercial and industrial uses
n miles BBBBBBSSSM kmbbbbbbsss north northwest of buffalo new york and
receded at the end of the wisconsin glaciation BBBBBBSSSTHE last ice agebbbbbbsss
more than six million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss of water falls
f million cubic feet BBBBBBSSSXYZKLM msbbbbbbsss on average it is the most
s miles BBBBBBSSSZ kmbbbbbbsss south southeast of toronto ontario
the niagara falls are renowned both for their BEAUTY and
has BEEN a challenge for the stewards of the falls since the tklms
straddling the international border BETWEEN the canadian province
BETWEEN the twin cities of niagara falls ontario
balance BETWEEN recreational commercial and industrial uses
straddling the international BORDER between the canadian province
canadian side of the BORDER and american falls on the
the niagara falls are renowned BOTH for their beauty and
american side the smaller BRIDAL veil falls are also
n miles bbbbbbsssm kmbbbbbbsss north northwest of BUFFALO new york and
of two major sections separated BY goat island:
BY luna island niagara falls were formed when glaciers
and water from the newly formed great lakes CARVED a path through
has been a CHALLENGE for the stewards of the falls since the tklms
between the twin CITIES of niagara falls ontario
balance between recreational COMMERCIAL and industrial uses
and niagara falls new york niagara falls is COMPOSED
over the CREST line every minute in high flow and almost
more than six million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million CUBIC feet bbbbbbsssxyzklm msbbbbbbsss on average it is the most
the niagara escarpment EN route to the atlantic ocean
receded at the END of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
the niagara ESCARPMENT en route to the atlantic ocean
over the crest line EVERY minute in high flow and almost
while not EXCEPTIONALLY high the niagara falls are very wide
F million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average it is the most
the niagara FALLS are voluminous waterfalls on the niagara river
of ontario and the u s state of new york the FALLS are
between the twin cities of niagara FALLS ontario
and niagara FALLS new york niagara falls is composed
and niagara falls new york niagara FALLS is composed
horseshoe FALLS the majority of which lies on the
canadian side of the border and american FALLS on the
american side the smaller bridal veil FALLS are also
located on the american side separated from the main FALLS
by luna island niagara FALLS were formed when glaciers
while not exceptionally high the niagara FALLS are very wide
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water FALLS
the niagara FALLS are renowned both for their beauty and
has been a challenge for the stewards of the FALLS since the tklms
more than six million cubic FEET bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic FEET bbbbbbsssxyzklm msbbbbbbsss on average it is the most
over the crest line every minute in high FLOW and almost
by luna island niagara falls were FORMED when glaciers
and water from the newly FORMED great lakes carved a path through
located on the american side separated FROM the main falls
and water FROM the newly formed great lakes carved a path through
receded at the end of the wisconsin GLACIATION bbbbbbsssthe last ice agebbbbbbsss
by luna island niagara falls were formed when GLACIERS
of two major sections separated by GOAT island:
HAS been a challenge for the stewards of the falls since the tklms
while not exceptionally HIGH the niagara falls are very wide
over the crest line every minute in HIGH flow and almost
HORSESHOE falls the majority of which lies on the
as a valuable source of HYDROELECTRIC power managing the
receded at the end of the wisconsin glaciation bbbbbbsssthe last ICE agebbbbbbsss
balance between recreational commercial and INDUSTRIAL uses
straddling the INTERNATIONAL border between the canadian province
by luna ISLAND niagara falls were formed when glaciers
of two major sections separated by goat ISLAND
n miles bbbbbbsssm KMBBBBBBSSS north northwest of buffalo new york and
s miles bbbbbbsssz KMBBBBBBSSS south southeast of toronto ontario
receded at the end of the wisconsin glaciation bbbbbbsssthe LAST ice agebbbbbbsss
horseshoe falls the majority of which LIES on the
over the crest LINE every minute in high flow and almost
LOCATED on the american side separated from the main falls
by LUNA island niagara falls were formed when glaciers
located on the american side separated from the MAIN falls
of two MAJOR sections separated by goat island:
horseshoe falls the MAJORITY of which lies on the
as a valuable source of hydroelectric power MANAGING the
n MILES bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
s MILES bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
more than six MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f MILLION cubic feet bbbbbbsssxyzklm msbbbbbbsss on average it is the most
over the crest line every MINUTE in high flow and almost
MORE than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
f million cubic feet bbbbbbsssxyzklm msbbbbbbsss on average it is the MOST
more than six million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS of water falls
f million cubic feet bbbbbbsssxyzklm MSBBBBBBSSS on average it is the most
N miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new york and
of ontario and the u s state of NEW york the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo NEW york and
and niagara falls NEW york niagara falls is composed
and water from the NEWLY formed great lakes carved a path through
the NIAGARA falls are voluminous waterfalls on the niagara river
the niagara falls are voluminous waterfalls on the NIAGARA river
between the twin cities of NIAGARA falls ontario
and NIAGARA falls new york niagara falls is composed
and niagara falls new york NIAGARA falls is composed
by luna island NIAGARA falls were formed when glaciers
the NIAGARA escarpment en route to the atlantic ocean
while not exceptionally high the NIAGARA falls are very wide
the NIAGARA falls are renowned both for their beauty and
n miles bbbbbbsssm kmbbbbbbsss NORTH northwest of buffalo new york and
powerful waterfall in NORTH america
n miles bbbbbbsssm kmbbbbbbsss north NORTHWEST of buffalo new york and
while NOT exceptionally high the niagara falls are very wide
the niagara escarpment en route to the atlantic OCEAN
OF ontario and the u s state of new york the falls are
of ontario and the u s state OF new york the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest OF buffalo new york and
s miles bbbbbbsssz kmbbbbbbsss south southeast OF toronto ontario
between the twin cities OF niagara falls ontario
OF two major sections separated by goat island:
horseshoe falls the majority OF which lies on the
canadian side OF the border and american falls on the
receded at the end OF the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss OF water falls
as a valuable source OF hydroelectric power managing the
has been a challenge for the stewards OF the falls since the tklms
of ONTARIO and the u s state of new york the falls are
s miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ONTARIO
between the twin cities of niagara falls ONTARIO
OVER the crest line every minute in high flow and almost
and water from the newly formed great lakes carved a PATH through
as a valuable source of hydroelectric POWER managing the
POWERFUL waterfall in north america
straddling the international border between the canadian PROVINCE
RECEDED at the end of the wisconsin glaciation bbbbbbsssthe last ice agebbbbbbsss
balance between RECREATIONAL commercial and industrial uses
the niagara falls are RENOWNED both for their beauty and
the niagara falls are voluminous waterfalls on the niagara RIVER
the niagara escarpment en ROUTE to the atlantic ocean
of ontario and the u S state of new york the falls are
S miles bbbbbbsssz kmbbbbbbsss south southeast of toronto ontario
of two major SECTIONS separated by goat island:
of two major sections SEPARATED by goat island:
located on the american side SEPARATED from the main falls
canadian SIDE of the border and american falls on the
american SIDE the smaller bridal veil falls are also
located on the american SIDE separated from the main falls
has been a challenge for the stewards of the falls SINCE the tklms
more than SIX million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
american side the SMALLER bridal veil falls are also
as a valuable SOURCE of hydroelectric power managing the
s miles bbbbbbsssz kmbbbbbbsss SOUTH southeast of toronto ontario
s miles bbbbbbsssz kmbbbbbbsss south SOUTHEAST of toronto ontario
of ontario and the u s STATE of new york the falls are
has been a challenge for the STEWARDS of the falls since the tklms
STRADDLING the international border between the canadian province
more THAN six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of water falls
the niagara falls are renowned both for THEIR beauty and
and water from the newly formed great lakes carved a path THROUGH
has been a challenge for the stewards of the falls since the TKLMS
the niagara escarpment en route TO the atlantic ocean
s miles bbbbbbsssz kmbbbbbbsss south southeast of TORONTO ontario
between the TWIN cities of niagara falls ontario
of TWO major sections separated by goat island:
of ontario and the U s state of new york the falls are
balance between recreational commercial and industrial USES
as a VALUABLE source of hydroelectric power managing the
american side the smaller bridal VEIL falls are also
while not exceptionally high the niagara falls are VERY wide
the niagara falls are VOLUMINOUS waterfalls on the niagara river
and WATER from the newly formed great lakes carved a path through
more than six million cubic feet bbbbbbsssxyzklm msbbbbbbsss of WATER falls
powerful WATERFALL in north america
the niagara falls are voluminous WATERFALLS on the niagara river
by luna island niagara falls WERE formed when glaciers
by luna island niagara falls were formed WHEN glaciers
horseshoe falls the majority of WHICH lies on the
WHILE not exceptionally high the niagara falls are very wide
while not exceptionally high the niagara falls are very WIDE
receded at the end of the WISCONSIN glaciation bbbbbbsssthe last ice agebbbbbbsss
of ontario and the u s state of new YORK the falls are
n miles bbbbbbsssm kmbbbbbbsss north northwest of buffalo new YORK and
and niagara falls new YORK niagara falls is composed
Code：
#define LOCAL
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
#define N 50
#define IGN 60
#define TN 210
#define WN 20
int cmp_kwd(const void *_a, const void *_b);
struct keywd
{
int h,ls;//指示在第几个句子，第几列
char wd[N];
keywd(){ h=ls=0; memset(wd,0,sizeof(wd));}
keywd(const char *s,int i,int j)
{
strcpy(wd,s);
h=i;
ls=j;
}
keywd operator=(const keywd &x)
{
strcpy(wd,x.wd);
h=x.h;
ls=x.ls;
return *this;
}
};
char ignwd[IGN][15];
char title[TN][WN][N];
int wordn[TN];//存储第i行有几个单词
keywd kwlist[6000];
int main()
{
#ifdef LOCAL
freopen("data123.in","r",stdin);
freopen("data123.out","w",stdout);
#endif
int ign=0;
while(scanf("%s",ignwd[ign++]) && ignwd[ign-1][0]!=‘:‘);
ign--;
//printf("ign:%d\n",ign);
//输入titles
getchar();
char c;
int hn=0,wn=0,ln=0;//指示title的行数、单词数、列数
while((c=getchar())!=EOF)
{
if(c==‘ ‘)
{//一个单词结束
if(ln==0) continue;
title[hn][wn][ln]=‘\0‘;
ln=0;
wn++;
}
else if(c==‘\n‘)
{
if(ln==0) continue;
title[hn][wn][ln]=‘\0‘;
wordn[hn]=wn+1;//这里应加1，因为当遇到换行符时也是一个单词结束
ln=0;
wn=0;
hn++;
}
else
{
title[hn][wn][ln++]=tolower(c);
}
}//while
title[hn][wn][ln]=‘\0‘;
wordn[hn]=wn+1;
hn++;//这里应加1，因为读到EOF时，title是多1行的。在cmd测试时，因为我是先按了回车再按ctrl+z，所以查不出这个错误
//printf("hn:%d\n",hn);
/*for(int i=0;i<hn;++i)
for(int j=0;j<wordn[i];++j)
{
printf("%s ",title[i][j]);
if(j==wordn[i]-1) printf("\n");
}*/
//判断keywords
int kwn=0;
for(int i=0;i<=hn;++i)
for(int j=0;j<=wordn[i];++j)
{
bool flag=1;//指示title[i][j]是否为keywords
if(strlen(title[i][j])==0) continue;
for(int k=0;k<ign;++k)
{
if(strcmp(title[i][j],ignwd[k])==0) { flag=0;break;}
}//fork
if(flag)
{
kwlist[kwn++]=keywd(title[i][j],i,j);
}//if
}
qsort(kwlist,kwn,sizeof(keywd),cmp_kwd);
for(int k=0;k<kwn;++k)
{
int x=kwlist[k].h;
int y=kwlist[k].ls;
for(int i=0;i<wordn[x];++i)
{
if(i==y)
{
for(int j=0;j<strlen(kwlist[k].wd);++j)
printf("%c",toupper(kwlist[k].wd[j]));
if(i!=wordn[x]-1) printf(" ");
else printf("\n");
}
else if(i!=wordn[x]-1) printf("%s ",title[x][i]);
else printf("%s\n",title[x][i]);
}//fori
}//fork
//system("pause");
return 0;
}
int cmp_kwd(const void *_a, const void *_b)
{
keywd *a=(keywd*)_a;
keywd *b=(keywd*)_b;
int c=strcmp(a->wd,b->wd);
if(c) return c;
else
{
if(a->h!=b->h) return a->h-b->h;
else return a->ls-b->ls;
}
}
原文：http://blog.csdn.net/buxizhizhou530/article/details/21737469