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

P6456 [COCI 2006/2007 #5] DVAPUT

题目描述

给定一个长度为L LL的字符串，你需要找出一个最长的子串，并且使得这个子串在字符串中出现了至少两次（在不同的位置）。输出它的长度。

输入格式

输入第一行一个整数L LL，表示字符串的长度。

第二行为一个长度为L LL的字符串。

输出格式

输出一行一个整数，表示这个最长串的长度。

输入输出样例 #1

输入 #1

11 sabcabcfabc

输出 #1

3

输入输出样例 #2

输入 #2

18 trutrutiktiktappop

输出 #2

4

输入输出样例 #3

输入 #3

6 abcdef

输出 #3

0

说明/提示

数据规模与约定

对于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++实现

#include<bits/stdc++.h>#defineintlonglong#defineullunsignedlonglongusingnamespacestd;constintN=2e5+10,Base=13331;intn;string s;ull pw[N],hs[N];intget_hs(intl,intr){returnhs[r]-hs[l-1]*pw[r-l+1];}boolcheck(intmid){if(mid==0)return1;unordered_set<ull>mp;for(inti=1;i+mid-1<=n;i++){ull hs=get_hs(i,i+mid-1);if(mp.count(hs))return1;mp.insert(hs);}return0;}signedmain(){cin.tie(0),cout.tie(0)->sync_with_stdio(false);cin>>n>>s;s=' '+s;pw[0]=1;for(inti=1;i<=n;i++){pw[i]=pw[i-1]*Base;hs[i]=hs[i-1]*Base+s[i];}intl=0,r=n+1;while(l+1<r){intmid=l+r>>1;if(check(mid))l=mid;elser=mid;}cout<<l;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容