打卡信奥刷题（3030）用C++实现信奥题 P6456 [COCI 2006/2007 #5] DVAPUT

P6456 [COCI 2006/2007 #5] DVAPUT题目描述给定一个长度为L LL的字符串你需要找出一个最长的子串并且使得这个子串在字符串中出现了至少两次在不同的位置。输出它的长度。输入格式输入第一行一个整数L LL表示字符串的长度。第二行为一个长度为L LL的字符串。输出格式输出一行一个整数表示这个最长串的长度。输入输出样例 #1输入 #111 sabcabcfabc输出 #13输入输出样例 #2输入 #218 trutrutiktiktappop输出 #24输入输出样例 #3输入 #36 abcdef输出 #30说明/提示数据规模与约定对于100 % 100\%100%的数据保证1 ≤ L ≤ 2 × 10 5 1\le L\le 2\times 10^51≤L≤2×105输入的字符串都为小写字母。说明题目译自 COCI2006-2007 CONTEST #5T6 DVAPUT。C实现#includebits/stdc.h#defineintlonglong#defineullunsignedlonglongusingnamespacestd;constintN2e510,Base13331;intn;string s;ull pw[N],hs[N];intget_hs(intl,intr){returnhs[r]-hs[l-1]*pw[r-l1];}boolcheck(intmid){if(mid0)return1;unordered_setullmp;for(inti1;imid-1n;i){ull hsget_hs(i,imid-1);if(mp.count(hs))return1;mp.insert(hs);}return0;}signedmain(){cin.tie(0),cout.tie(0)-sync_with_stdio(false);cinns;s s;pw[0]1;for(inti1;in;i){pw[i]pw[i-1]*Base;hs[i]hs[i-1]*Bases[i];}intl0,rn1;while(l1r){intmidlr1;if(check(mid))lmid;elsermid;}coutl;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容