`
woxiaoe
  • 浏览: 282749 次
  • 性别: Icon_minigender_1
  • 来自: 长沙
社区版块
存档分类
最新评论

POJ 2406(KMP 算法的应用)

    博客分类:
  • ACM
阅读更多

题目地址:http://acm.pku.edu.cn/JudgeOnline/problem?id=2406
题目要求一个串的最大重复次数:

abcd 1

aaaa 4

ababab 3

 

这题可用kmp算法。有串p

next[j] = k,说明 p0pk == pj-k-1pj-1,也就是说k为其前面相等串的长度。所以我们通过字符串最后一个字符的next值就可以得到字符串的重复次数。

package com.woxiaoe.acm.pku.P2406;

import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {

		//Scanner scn = new Scanner(System.in);
		Scanner scn = new Scanner(Main.class.getResourceAsStream("in.dat"));
		PrintWriter out = new PrintWriter(System.out);
		String input = "";
		List<String> inputs = new ArrayList<String>(5000);
		int index = 0;
		while(scn.hasNext()){
			input = scn.next();
			/*if(input.equals(".")){
				break;
			}*/
			index ++;
			inputs.add(input);
		}
		index --;
		for(int i = 0; i < index; i++ ){
			out.println(kmp(inputs.get(i)));
		}
		out.flush();
	}

	private static int kmp(String input) {
		int len = input.length();
		//char[] pattern = new char[len + 1];
		int[] next = new int[len + 1];
		//System.arraycopy(input.toCharArray(), 0, pattern, 1, len);
		int i = 0,j = -1;
		next[0] = -1;
		while(i < len){
			if( j == -1 || input.charAt(i) == input.charAt(j)){
				i++;
				j++;
				next[i] = j;
			}else{
				j = next[j];
			}
		}
		/*if(len == 2 && pattern[1] == pattern[2]){
			return 2;
		}*/
		if(len % (len - next[len]) == 0){
			return len /(len - next[len]);
		}
		return 1;
	}
}
 
分享到:
评论

相关推荐

    KMP.rar_kmp poj

    《KMP算法在POJ题目中的应用》 KMP(Knuth-Morris-Pratt)算法,是一种在字符串中寻找子串的搜索算法,由Donald Knuth、Vaughan Pratt和James H. Morris三位学者于1970年代提出。在编程竞赛如POJ(Problemset On...

    北大POJ初级-基本算法

    7. **字符串处理**:如KMP算法、Rabin-Karp算法、Boyer-Moore算法等,用于高效地进行字符串匹配。 8. **回溯与分支限界**:用于解决组合优化问题,如八皇后问题、N皇后问题、旅行商问题等。 9. **数据结构**:如数...

    北大POJ中级-基本算法

    5. 字符串处理:KMP算法、Rabin-Karp算法等,对于字符串匹配问题至关重要。 6. 数组与链表:数据结构基础,理解和熟练操作数组和链表是解决算法问题的前提。 二、解题策略与AC代码分析 在POJ的中级算法中,我们通常...

    ACM-POJ 算法训练指南

    5. **字符串匹配**:如KMP算法(poj1961, poj2406)。 ### 十三、进阶算法 1. **组合优化**:如割平面法、分支定界法等(poj3411, poj1724)。 2. **近似算法**:解决NP难问题时的近似求解方法(poj3373, poj1691...

    POJ 分类题目 txt文件

    例如,题目poj1961和poj2406就是KMP算法的应用实例。 ### 7. 几何算法 几何算法涉及点、线、面的性质和关系,如凸包、最近点对、三角剖分等问题。这些算法在计算机图形学、地理信息系统等领域有着广泛的应用。例如...

    poj题目分类

    * KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 * 记忆化搜索:例如 poj3373、poj1691。 5. 动态规划: * 较为复杂的动态规划:...

    ACMer需要掌握的算法讲解 (2).docx

    * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、POJ3034 * 记录状态的动态规划:POJ3254、...

    经典 的POJ 分类

    - POJ 1961、POJ 2406:KMP算法的应用。 ### 其他问题 #### 贪心算法 - **题目示例**: - POJ 3411、POJ 1724:贪心策略的选择与应用。 #### 二分查找 - **题目示例**: - POJ 3373、POJ 1691:二分查找技术的...

    ACM常用算法及其相应的练习题.docx

    ACM常用算法及其相应的练习题 本资源总结了 ACM 竞赛中常用的算法和相应的练习题,涵盖了基础算法、图...* KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 * 搜索的技巧和优化 + poj3411, poj1724

    poj训练计划.doc

    - 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...

    acm训练计划(poj的题)

    6. **KMP算法**: - (poj1961, poj2406):高效的字符串匹配算法。 ### 十、进阶状态压缩 1. **状态压缩技巧**: - 如何高效地表示和压缩状态。 2. **状态压缩优化**: - (poj3411, poj1724):进一步提高状态...

    poj各种分类

    如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合...

    ACMer需要掌握的算法讲解.docx

    3. KMP 算法(poj1961, poj2406) 4. 左偏树(可合并堆) 四、搜索 1. 最优化剪枝和可行性剪枝 2. 较为复杂的动态规划(如动态规划解特别的施行商问题等) 3. 记录状态的动态规划 4. 树型动态规划 五、计算几何学...

    算法训练方案详解

    - **应用场景**: 测试对算法的理解和实现能力。 - **示例题目**: POJ 3393, POJ 1472, POJ 3371, POJ 1027, POJ 2706 - **注意事项**: 细致地分析题目需求。 #### 二、图算法 **1. 差分约束系统** - **定义**:...

    POJ 我收集的解题报告(100多道)

    7. **字符串处理**:KMP算法、Rabin-Karp算法、Manacher's Algorithm等。 8. **模拟法**:按照题目描述进行程序设计,模拟实际情况。 9. **编码技巧**:如位操作、动态类型、模板等,以提高代码效率或简洁性。 ...

    acm poj300题分层训练

    7. **数学**:poj1286、poj2409等继续深入组合数学,poj1226、poj1961等训练了KMP算法,poj3440、poj3071等涉及概率问题和高斯消元法。 这个训练计划通过精心挑选的题目,逐步提升编程者的算法思维和实现能力,为...

    poj大量习题详解ACM

    4. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法等字符串匹配方法,以及字符串操作(子串查找、模式匹配、字符串反转等)。 5. **编码技巧**:IO流的高效处理(缓冲区读写、文件流、字符编码等)、位...

    string-problem(POJ).rar_POJ 19_poj

    2. **POJ1790**:可能涉及字符串的模式匹配,如KMP算法或Boyer-Moore算法,用于在一个字符串中寻找另一个字符串的出现位置。 3. **POJ1951**:可能与字符串的排序有关,比如可以运用Manacher's Algorithm解决最长...

    acm新手刷题攻略之poj

    - 字符串匹配算法如KMP算法可以提高字符串匹配的效率。 以上列举的题目只是冰山一角,POJ上还有更多类型的题目等待着大家去探索。通过不断练习这些题目,可以逐渐建立起解决各类问题的能力,为参加更高级别的竞赛...

    poj acm300题 c++源码打包

    5. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法等字符串匹配方法。 6. **位运算**:利用位运算进行高效计算,如快速幂、异或操作等。 7. **优化技巧**:如代码优化、内存管理、预处理指令、递归...

Global site tag (gtag.js) - Google Analytics