首页 > 代码库 > [COGS 2688]鱼的感恩
[COGS 2688]鱼的感恩
[COGS 2688]鱼的感恩
题目
从前有一个渔夫抓到了一条特别的鱼，放走了。
渔夫再次抓到了这条鱼，正要再次放走之时，这条鱼吐出了一片迷雾，迷雾散去以后，渔夫不见了。
渔夫睁开眼，发现自己到了一个石碑面前，碑上有一行小写英文字符串S，下面写着：“汝等既有护生之念，应是善良之人，理当授以嘉奖。但是为了证明你的善良，你需要展现你的智慧，以确保吾所见之善良，并非出于汝之愚笨。上面的字符串，你若于其中找到最长的子串，使得这个子串既出现在前缀，又出现在后缀，还出现在字符串的中间，也就是既非前缀又非后缀的位置，则该石碑会将其所藏之物拱手相送。”
渔夫听完以后，可谓一脸懵逼，遂将这个问题分享给你，希望你能够解决。若能解决，渔夫愿意拿出10,000,000,000,000 mod 250 元，作为解决这个问题的报酬。
INPUT
第一行是一个数字q，表示这个问题有q组不同问题。
接下来q行每行一个由小写英文字母组成的字符串S，意义见于上文。
OUTPUT
输出共q行，每行一个字符串，表示对于每组问题，所求的字符串，如果不存在长度大于0且满足要求的字符串，就改成输出”---”（不包含引号）
SAMPLE
INPUT
1
niconiconi
OUTPUT
ni
解题报告
考试时打了个纯暴力，竟然骗了70= =
正解1：
kmp乱搞，求一下next数组，记录在1~n-1哪些next出现过，在n一直跳next，直到出现过即是答案（话说这是标算吧啊喂）
正解2：
hash乱搞（这才是真正的乱搞吧啊喂），先用p进制搞出整个的hash值，然后从后往前枚举终点，然后用这个前缀去匹配
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<vector> 5 using namespace std; 6 typedef unsigned long long L; 7 const int p=233; 8 char s[100005]; 9 L xp[100005],h[100005];10 int len;11 vector<int>po;12 inline bool judge(int pos){13 if(s[len-1]!=s[pos-1])14 return false;15 L cmp_has(h[0]-h[pos]*xp[pos]),pre_has(h[len-pos]);16 if(cmp_has!=pre_has)17 return false;18 for(int i=0;i<po.size();i++){19 int tp(po[i]);20 if(tp+pos>=len)21 return false;22 L mid_has(h[tp]-h[tp+pos]*xp[pos]);23 if(mid_has==cmp_has)24 return true;25 }26 return false;27 }28 int main(){29 freopen("fool.in","r",stdin);30 freopen("fool.out","w",stdout);31 int n;32 scanf("%d",&n);33 while(n--){34 memset(h,0,sizeof(h));35 scanf("%s",s);36 len=strlen(s);37 xp[0]=1;38 for(int i=1;i<=len;i++)39 xp[i]=xp[i-1]*p;40 po.clear();41 for(int i=1;i<len;i++)42 if(s[i]==s[0])43 po.push_back(i);44 for(int i=len-1;i>=0;i--)45 h[i]=h[i+1]*p+s[i]-‘a‘;46 int tmp(0);47 for(int i=len-2;i>=0;i--){48 if(judge(i)){49 tmp=i;50 break;51 }52 }53 if(!tmp)54 puts("---");55 else{56 for(int i=0;i<tmp;i++)57 putchar(s[i]);58 putchar(‘\n‘);59 }60 }61 }
[COGS 2688]鱼的感恩
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。