思想
字符串哈希+二分。这里为了提升字符串哈希的准确性,用131和233两个质数做哈希表。然后考虑到二段性,用二分来找最长的不重叠字符串。
代码
import java.io.*;
import java.util.Map;
import java.util.HashMap;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static Map<Long, Integer> mp1 = new HashMap<>(); //记录字符串前缀哈希首字母出现的位置
static Map<Long, Integer> mp2 = new HashMap<>();
static int N = 100010, n; //为了保证字符串哈希的有效性,这里用了两个质数来计算字符串哈希
static long P1=131, P2 = 233, Q = Long.MAX_VALUE;
static long[] h1 = new long[N];
static long[] h2 = new long[N];
static long[] p1 = new long[N];
static long[] p2 = new long[N];
//寻找是否存在长度为len的两个不重叠的字符串
public static boolean check(int len){
for(int i=1; i+len-1<=n; i++){
int l = i, r = i+len-1;
long hash1 = get1(l, r), hash2 = get2(l, r);
//如果存在哈希,就判断是否重叠,否则累计
if(mp1.containsKey(hash1) && mp2.containsKey(hash2)){
int pos1 = mp1.get(hash1), pos2 = mp2.get(hash2);
if(pos1+len-1<i && pos2+len-1<i) return true;
}else{
mp1.put(hash1, l);
mp2.put(hash2, l);
}
}
return false;
}
public static long get1(int l, int r){
return (h1[r]-h1[l-1]*p1[r-l+1]);
}
public static long get2(int l, int r){
return (h2[r]-h2[l-1]*p2[r-l+1]);
}
public static void main(String[] args)throws IOException{
String s = " "+in.readLine();
char[] c = s.toCharArray();
n = c.length-1;
//计算两组字符串哈希
p1[0] = p2[0] = 1;
for(int i=1; i<=n; i++){
p1[i] = (p1[i-1]*P1)%Q;
p2[i] = (p2[i-1]*P2)%Q;
h1[i] = ((h1[i-1]*P1)%Q+c[i])%Q;
h2[i] = ((h2[i-1]*P2)%Q+c[i])%Q;
}
//二分找最大且不重叠的字符串
int l = 1, r = n;
while(l<r){
int mid = l+r+1>>1;
if(check(mid)) l=mid;
else r = mid-1;
}
out.println(r);
out.flush();
out.close();
}
}