一个字符串处理的问题,做法是排序+二分查找。地址: http://acm.pku.edu.cn/JudgeOnline/problem?id=1318
#include < stdio.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < stdlib.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include < string.h >
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
typedef struct
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
char unch[8];
char ch[8];
}type;
type word[101];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp1 ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return *( char * )a - *( char * )b;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int cmp2 ( const void *a, const void *b )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
type *c = ( type * )a;
type *d = ( type * )b;
int ans;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
ans = strcmp ( c->ch, d->ch );
if ( !ans )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return strcmp ( c->unch, d->unch );
}
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void sort ( int n )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
for ( int i=0; i<n; i++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
qsort ( word[i].ch, strlen( word[i].ch ), sizeof( char ), cmp1 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
qsort ( word, n, sizeof( type ), cmp2 );
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int main ()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
char input[8];
char end[] = "XXXXXX";
int n;
type in;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
n = 0;
while ( scanf ( "%s", input ) != EOF && strcmp( input, end ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
strcpy ( word[n].unch, input );
strcpy ( word[n].ch, input );
n ++;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
sort ( n );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( scanf ( "%s", input ) != EOF && strcmp( input, end ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int left, right, middle;
left = 0; right = n-1;
strcpy ( in.unch, input );
strcpy ( in.ch, input );
qsort ( in.ch, strlen ( in.ch ), sizeof( char ), cmp1 );
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
while ( left <=right )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
middle = ( left + right ) / 2;
if ( strcmp ( word[middle].ch, in.ch ) >=0 )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
right = middle - 1;
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
left = middle + 1;
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
if ( left < n && ( ! strcmp ( word[left].ch, in.ch ) ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int low, high;
low = left; high = left;
while ( low > 0 && ( ! strcmp ( word[low - 1].ch, in.ch ) ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
low --;
}
while ( high < n-1 && ( ! strcmp ( word[high+1].ch, in.ch ) ) )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
high ++;
}
for ( ; low<=high; low ++ )
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf( "%s\n", word[low].unch );
}
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
printf ( "NOT A VALID WORD\n" );
}
printf ( "******\n" );
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return 0;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
公告
决定从线程开始!!
常用链接
留言簿(6)
随笔档案
搜索
最新评论
![](/images/xml.gif)
阅读排行榜
评论排行榜
|
|