链接:
UVa : http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1828
类型: 哈希表
原题:
A language is a set of strings. And the concatenation of two languages is the set of all strings that are formed by concatenating the strings of the second language at the end of the strings of the first language.
For example, if we have two language A and B such that:
A= {cat, dog, mouse}
B= {rat, bat}
The concatenation of A and B would be:
C= {catrat, catbat, dograt, dogbat, mouserat, mousebat}
Given two languages your task is only to count the number of strings in the concatenation of the two languages.
样例输入;
2
3 2
cat
dog
mouse
rat
bat
1 1
abc
cab
样例输出:
Case 1: 6
Case 2: 1
题目大意:
有单词集合A和集合B, 然后有这两个集合可以组成新的复合词,其中A中的是复合词的前半部分,B中的是后半部分。给出A,B两集合,问最多能组合出多少个符合单词?
分析与总结:
这题感觉就是UVa
10391 - Compound Words的兄弟篇, 挺像的。
还是用哈希来判重。没组出一个新单词就尝试加入哈希表中, 如果成功加入,那么就加1。
这题因为滥用memcmp和memspy来处理字符串而WA了多次。
还有一个很坑爹的,读入单词要用gets, 因为有可能是有空行的单词....
/*
* Uva 10887 - Concatenation of Languages
* 哈希表
* Time: 0.404s (UVa)
* Author: D_Double
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 1503
using namespace std;
char A[MAXN][12], C[MAXN*MAXN][24];
const int HashSize = MAXN*MAXN;
int head[HashSize], next[HashSize], rear, ans;
inline void init(){ rear=1; ans=0; memset(head, 0, sizeof(head)); }
inline int hash(char *str){
int seed=131, v=0;
while(*str) v = v*seed + (*str++);
return (v & 0x7FFFFFFF)%HashSize;
}
int try_to_insert(int s){
int h = hash(C[s]);
int u = head[h];
while(u){
if(strcmp(C[u], C[s])==0) return 0;
u = next[u];
}
next[s] = head[h];
head[h] = s;
return 1;
}
int main(){
int T, M, N, cas=1;
scanf("%d%*c", &T);
while(T--){
scanf("%d %d%*c",&M,&N);
for(int i=0; i<M; ++i) gets(A[i]);
init();
char str[12], link_word[24];
for(int j=0; j<N; ++j){
gets(str);
for(int i=0; i<M; ++i){
strcpy(link_word, A[i]);
strcat(link_word, str);
strcpy(C[rear], link_word);
if(try_to_insert(rear)){ ++rear; ++ans; }
}
}
printf("Case %d: %d\n", cas++, ans);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
代码
翻译的内容有:Clc、ans、Calling Functions、Character Strings、Tutorials - workspace variables、Tutorials - array indexing、Tutorials - matrices and arrays- Concatenation and Complex Numbers、Tutorials...
串联
卷积码和BCH码级联系统基于格图的迭代译码,安乐,,本文提出一种外码为BCH码,内码为卷积码的级联码迭代译码方案。对于外码使用基于格图的软输出维特比译码算法,对于内码使用修正的
This test checks if repeated string concatenation causes an exception (and not a crash).
A Serial Concatenation-Based Coding Scheme for Dimmable Visible Light Communication Systems
You are visitor as of October 17, 1996. The Art of Assembly Language Programming <br>Forward Why Would Anyone Learn This Stuff? 1 What's Wrong With Assembly Language 2 What's Right With ...
Concatenation 层初始例代码初始例代码输张量形状 (1,3,4,5)from cuda import cudartimport tensorrt a
class relative to the repeated concatenation of strings, and then discuss the theoretical underpinnings of its amortized performance. • We provide increased discussion of iterators, contrasting ...
最新版J2EE+-+Multiple+Choice___ssd3参考答案,我的教材和它完全一样。 1. Which method must ... Which of the following is the string concatenation operator in Java? (a) + (b) ^ (c) & (d) ++
Efficient Post-Concatenation of Transformation Matrices (770) 476GRAPHICS GEMS I Edited by ANDREW S. GLASSNER xiii CONTENTS 10 MODELING AND TRANSFORMATIONS Transformation Identities 485 Fixed-Point ...
Five Matlab codes corresponding to the concatenation of mat files, importing multiple files at a time, down-sampling, up-sampling of a signal and finally a code which except unique one removes all ...
有一次在看论文的时候(Multi-Range Attentive Bicomponent Graph Convolutional Network for Traffic Forecasting),在公式里遇到concatenation operation,不知道是什么,大致的意思应该是把向量中对应位置加起来...
chap6 - fundamentals of synchronization chap7 - Time-Varying Channels and Adaptive Transmission Systems chap8 - Coding and Multi-User chap9 - Decoding Algorithms chap10 - Channel Coding chap11 - Code ...
The number of questions is increasing recently. Here is the classification of all `468` questions. For more questions and solutions, you can see my [LintCode](https://github.com/kamyu104/LintCode) ...
This file is a concatenation of the queries files originally released in LDC2011E46 (sample) and LDC2011E55 (training). This file contains 2171 queries. Each query entry consists of the following...
concatenation of the title, first name, lastname (i.e., "Mr. Michael Zheng") casualName() return the nickname if it is not null, otherwise return the first name (i.e., "Mike") Be realistic when ...
Here is a summary of all changes that have been made in each version of BurnInTest. Release 5.3 build 1035 revision 4 WIN32 release 10 November 2008 - Lenovo China specific build. Lenovo system ...
called the blocks, whose concatenation is equal to A. Given a partition P of a string A and a partition Q of a string B, we say that the pair hP, Qi is a common partition of A and B if Q is a ...