（Java实现）蓝桥杯国赛重复模式

标题：重复模式

作为 drd 的好朋友，技术男 atm 在 drd 生日时送给他一个超长字符串 S 。atm 要 drd 在其中找出一个最长的字符串 T ，使得 T 在 S 中至少出现了两次，而他想说的秘密就藏在 T 中。

由于字符串实在是太长了，drd 总是找不到合适的 T 。于是 drd 请你帮他找到这个 T 的长度。

【输入格式】

一行。一个字符串，即题目中说的S 。

【输出格式】

一行。一个整数，表示最长的 T 的长度。

【样例输入】

ababa

【样例输出】

3

「数据范围」

对于 30% 的数据，S长度 <= 100

对于 60% 的数据，S长度 <= 8000

对于 100% 的数据，S长度 <= 500000

资源约定：

峰值内存消耗 < 256M

CPU消耗 < 1000ms

他找重复的字符串就需要找相同开头

把每一种都取出来放在数组里面，把他们按照字典序排序，

数组上下基本上把相同开头的都匹配到了

直接for循环，把每一个相邻的字符串匹配一下看看最长的重复字符串是多少，记录一下

大概就是这个意思吧，要不然数据规模太大了

import java.util.Arrays;

import java.util.Scanner;

public class chongfumoshi2 {

	public static void main(String[] args) {

		// TODO 自动生成的方法存根

		Scanner sc = new Scanner(System.in);

		String input = sc.nextLine();

		String[] subString = new String[input.length()];

		for (int i = 0; i < subString.length; i++) {

			subString[i] = input.substring(i);

		}

		Arrays.sort(subString);

		// 排序后输出

		for (int i = 0; i < subString.length; i++) {

			System.out.println(subString[i]);

		}

		int maxLen = 0;

		for (int i = 0; i < input.length() - 1; i++) {

			int preLen = preLen(subString[i], subString[i + 1]);

			if (preLen > maxLen) {

				maxLen = preLen;

			}

		}

		System.out.println(maxLen);

	}

	public static int preLen(String s1, String s2) {

		int n = 0;

		int minLen = s1.length() < s2.length() ? s1.length() : s2.length();

		while (n < minLen && s1.charAt(n) == s2.charAt(n)) {

			n++;

		}

		return n;

	}

	}

巴特西

（Java实现）蓝桥杯国赛重复模式

最新文章

热门文章

巴特西

（Java实现） 蓝桥杯 国赛 重复模式

最新文章

热门文章

（Java实现）蓝桥杯国赛重复模式