/*
题意:一组单词,是否可以分解成两个单词
思路:可以进行重组(一种时间效率为n,但空间分配为n*n,一种时间效率为n*n,空间分配为n)
也可以进行分拆,效率为n*m,其中m为单词平均长度。
主要学习:字符串的哈希处理
另外看别人的代码学习到的新技巧:
char str[n][m];
int r[n];
借助r来实现对str的排序。
步骤:
for(int i=0;i<n;i++)
r[i]=i;
qsort(r,n,sizeof(r[0]),cmp);
for(int i=0;i<n;i++)
printf("%s\n",str[r[i]]);
其中:
int cmp(const void *a,const void *b)
{
int *pa=(int *)a;
int *pb=(int *)b;
return strcmp(str[pa],str[pb]);
}
*/
#include <cstdio>
#include <cstring>
const int nMax=120007;
int head[nMax],next[nMax];
char str[nMax][100];
int hash(char *a)
{
int u=0;
while(*a)
{
u=u*26+*a;
a++;
}
return (u & 0x7fffffff)%nMax;
}
void insert(int k)
{
int h=hash(str[k]);
next[k]=head[h];
head[h]=k;
}
bool search(char *a)
{
int h=hash(a);
int ok=false;
for(int i=head[h];i!=-1;i=next[i])
if(strcmp(str[i],a)==0)
{
ok=true;
break;
}
return ok;
}
int main()
{
//freopen("data.in","r",stdin);
int n=0;
memset(head,-1,sizeof(head));
while(gets(str[n]))
{
insert(n);
n++;
}
for(int i=0;i<n;i++)
{
for(int j=1;j<strlen(str[i]);j++)
{
char str1[100],str2[100];
memset(str1,0,sizeof(str1));
memset(str2,0,sizeof(str2));
strncpy(str1,str[i],j);
strncpy(str2,str[i]+j,strlen(str[i])-j);
if(search(str1) && search(str2))
{
printf("%s\n",str[i]);
break;//原来这里忘了跳出,一直WA。正所谓细节决定成败!
}
}
}
return 0;
}
第二次做:
#include <cstdio>
#include <cstring>
const int nMax=120000+10;
const int HASH=10000000;
char words[nMax][50];
int hash[HASH],next[HASH];
int get_hash(char word[])
{
int num,len;
len=strlen(word);
num=0;
for(int i=0;i<len;i++)
num=num*10+word[i];
return (num & 0x7fffffff)%HASH;
}
bool is_find(char a[])
{
int p=get_hash(a);
p=hash[p];
while(p!=-1)
{
if(strcmp(words[p],a)==0) return true;
p=next[p];
}
return false;
}
bool handle(int k)
{
int len=strlen(words[k]);
for(int i=1;i<len;i++)
{
char a[50],b[50];
strncpy(a,words[k],i);
a[i]=0;
strncpy(b,words[k]+i,len-i);
b[len-i]=0;
if(is_find(a) && is_find(b))
return true;
}
return false;
}
int main()
{
//freopen("f://data.in","r",stdin);
int n=0;
memset(hash,-1,sizeof(hash));
memset(next,-1,sizeof(next));
while(scanf("%s",words[n])==1)
{
int p=get_hash(words[n]);
next[n]=hash[p];
hash[p]=n;
n++;
}
for(int i=0;i<n;i++)
if(handle(i))
printf("%s\n",words[i]);
return 0;
}
分享到:
相关推荐
This powerful, practical book, based on years of proven and profi table experience, shows ... The Compound Effect is a treasure chest of ideas for achieving greater success than you ever thought possible
用法从下载二进制文件mkdir bybit && cd bybitwget https://github.com/tacotokyo/bybit-auto-compound/releases/download/v0.4/bybit-auto-compound-linuxchmod +x bybit-auto-compound-linux将.env.example文件...
cytoscape化合物拖放描述用于添加和删除子项的复合节点拖放UI( )依存关系Cytoscape.js ^ 3.4.0使用说明下载库: 通过npm: npm install cytoscape-compound-drag-and-drop , 通过凉亭: bower install cytoscape-...
compound words
React Compound Slider是一个小的滑块组件,对标记或样式没有意见。 2020年路线图 基本概述: 将滑块源转换为Typescript(完成) 将测试转换为打字稿(完成) 将演示和文档转换为Typescript(完成) 在内部使用...
CP-Macrocyclic-host-compound-analysis
shirisha-simple-and-compound-intrest
React复合计时器计时器复合组件,用于进行响应和本机响应,以减少构建计时器的痛苦。 它封装了所有计时器逻辑-您只需要考虑渲染!远期计数只需渲染一个简单的计时器,然后从0开始向前计数即可。...
adv-ng-patterns-02-compound-components-qpvvgh
terraform-aws-cloudfront-化合物 Terraform模块通过...用法创建一个文件调用module.cloudfront.tf : module " cloudfront " { source = " jameswoolfenden/aws/cloudfront-compound " versioning = var . versioning
晶体中堆积作用诱导[Ni(mnt)2]2-形成严重扭曲的非平面分子结构,陈梦雅,宁为华,在功能材料领域中,金属二硫烯电荷转移盐具有广泛应用。在本研究中,一种新型金属二硫烯基电荷转移盐[CF3-BzNH2Py]2[Ni(mnt)2]被合成...
Compound statement missing{ --------------------分程序漏掉"{" Conflicting type modifiers ------------------不明确的类型说明符 Constant expression required ----------------要求常量表达式 Constant ...
最小化内部版本,文件名包含哈希值。 您的应用已准备好进行部署! 有关更多信息,请参见关于的部分。 npm run eject 注意:这是单向操作。 eject ,您将无法返回! 如果您对构建工具和配置选择不满意,则可以...
复合文件结构查看工具的代码,内含复合文件格式定义。
多步zawiera wszystkie组件należące做复合组件
β-二亚胺配体支持的铝氧硼六元环化合物的合成、表征及其热稳定性研究,郝朋飞,杨智,LAlH2 (L = HC(CMeNAr)2, Ar = 2, 6-iPr2C6H3) (1) 与2-三氟甲基苯硼酸反应, 合成含铝氧硼六元环的化合物LAl[OB(2-CF3C6H4)]2...
ISO 4384-1-2000 滑动轴承-轴承金属的硬度测试 Plain bearings -- Hardness testing of bearing metals -- Part 1 Compound materials.rar
最长的化合物 最长组合结果
CP-大环-宿主-化合物分析用于识别和测量大环主体化合物大小的CellProfiler(版本4.0.3)管道
化合物复合Raydium Fusion池的脚本警告该软件未经审核-使用后果自负。 警告:此脚本将使用合并帐户中的所有资金进行复利先决条件您的钱包中必须有SOL,才能支付发送费用。 您必须将资金存入Raydium.io的Fusion Pools...