UVA - 10391 Compound Words （字符串hash）

2019-11-06 08:05:08

字体：大中小

来源：转载

供稿：网友

题意：找出由两个字符串拼起来的字符串输出暴力搜索切点分开字符串，查找有没有两断都存在的通过字符串hash散列 AC代码

#include<stdio.h>#include<string.h>char a[120500][20];int head[120500];int next1[120500];int get_hash(char *s){ int hash=0; int seed=131; for(int i=0;s[i]!='/0';i++) { hash=hash*seed+(s[i]-'a'); } return (hash & 0x7FFFFFFF)%100007;}void add_hash(int s){ int h=get_hash(a[s]); //PRintf("%d %d/n",h,s); next1[s]=head[h]; head[h]=s;}int main(){ int t=0; memset(head,-1,sizeof(head)); memset(next1,-1,sizeof(next1)); while(scanf("%s",a[t]),a[t][0]!='/0') { add_hash(t); t++; } char str1[20],str2[20]; for(int i=0;i<t;i++) { for(int j=0;a[i][j+1]!='/0';j++) { str1[j]=a[i][j]; str1[j+1]='/0'; int h1=get_hash(str1); h1=head[h1]; int flog=0; while(h1!=-1) { if(strcmp(a[h1],str1)==0) { int k; for( k=0;a[i][j+1+k]!='/0';k++) str2[k]=a[i][j+1+k]; str2[k]='/0'; int h2=get_hash(str2); h2=head[h2]; while(h2!=-1) { if(strcmp(a[h2],str2)==0) { printf("%s/n",a[i]); flog=1; break; } h2=next1[h2]; } if(flog) break; } h1=next1[h1]; } if(flog) break; } }}

上一篇：十二、####

下一篇：13（多线程）