重复模式－－蓝桥杯国赛历年真题

标题：重复模式     作为 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 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。 所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。 注意: main函数需要返回0 注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。 注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。

提交时，注意选择所期望的编译器类型。

思路：依次从字符串第i个字符开始，查找长度为j（1～n）的子串是否还存在与剩下（i+1到字符串尾）的字串中。说不清楚，看图。。。

代码： package 总决赛; import java.io.*; import java.util.Scanner; public class 重复模式 { static boolean find(String s,String c){//s中查找c int j = 0; for(int i=0;i<s.length();i++){ if(j == 0 && (s.length()-i)<c.length()) return false; if(s.charAt(i) == c.charAt(j)){ j++; if(j == c.length()) return true; }else{ j = 0; } } return false; } public static void main(String[] args) { // TODO Auto-generated method stub Scanner sc = new Scanner(System.in); String s = sc.next(); int max = 0; for(int i=0;i<s.length()-1;i++){ for(int j=1;j<=s.length()-i;j++){ // System.out.println(i+" "+s.substring(i,i+j)); if(find(s.substring(i+1),s.substring(i,i+j))){ max = j>max?j:max; } } } System.out.print(max); } }