package com.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * LeetCode1062_最长重复子串
 */
public class LeetCode1062 {
	public static int longestRepeatingSubString(String s) {
		int l = 0, r = s.length() - 1;
		while (l < r) {
			int mid = l + (r - l + 1) / 2;
			if (f(s, mid)) {
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		return l;
	}

	private static boolean f(String s, int length) {
		Set<String> seen = new HashSet<>();// 查重

		for (int i = 0; i <= s.length() - length; i++) {
			int j = i + length - 1;
			String sub = s.substring(i, j + 1);
			if (seen.contains(sub)) {
				return true;
			}
			seen.add(sub);
		}
		return false;
	}

	public static void main(String[] args) {
		String str1 = "abcd";
		System.out.println("result:" + longestRepeatingSubString(str1));

		String str2 = "abbaba";
		System.out.println("result:" + longestRepeatingSubString(str2));

		String str3 = "aabcaabdaab";
		System.out.println("result:" + longestRepeatingSubString(str3));

		String str4 = "aaaaa";
		System.out.println("result:" + longestRepeatingSubString(str4));

	}
}