[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 }