题目地址: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算法在POJ题目中的应用》 KMP(Knuth-Morris-Pratt)算法,是一种在字符串中寻找子串的搜索算法,由Donald Knuth、Vaughan Pratt和James H. Morris三位学者于1970年代提出。在编程竞赛如POJ(Problemset On...
7. **字符串处理**:如KMP算法、Rabin-Karp算法、Boyer-Moore算法等,用于高效地进行字符串匹配。 8. **回溯与分支限界**:用于解决组合优化问题,如八皇后问题、N皇后问题、旅行商问题等。 9. **数据结构**:如数...
5. 字符串处理:KMP算法、Rabin-Karp算法等,对于字符串匹配问题至关重要。 6. 数组与链表:数据结构基础,理解和熟练操作数组和链表是解决算法问题的前提。 二、解题策略与AC代码分析 在POJ的中级算法中,我们通常...
5. **字符串匹配**:如KMP算法(poj1961, poj2406)。 ### 十三、进阶算法 1. **组合优化**:如割平面法、分支定界法等(poj3411, poj1724)。 2. **近似算法**:解决NP难问题时的近似求解方法(poj3373, poj1691...
例如,题目poj1961和poj2406就是KMP算法的应用实例。 ### 7. 几何算法 几何算法涉及点、线、面的性质和关系,如凸包、最近点对、三角剖分等问题。这些算法在计算机图形学、地理信息系统等领域有着广泛的应用。例如...
* KMP 算法:例如 poj1961、poj2406。 4. 搜索: * 最优化剪枝和可行性剪枝。 * 搜索的技巧和优化:例如 poj3411、poj1724。 * 记忆化搜索:例如 poj3373、poj1691。 5. 动态规划: * 较为复杂的动态规划:...
* KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、POJ3034 * 记录状态的动态规划:POJ3254、...
- POJ 1961、POJ 2406:KMP算法的应用。 ### 其他问题 #### 贪心算法 - **题目示例**: - POJ 3411、POJ 1724:贪心策略的选择与应用。 #### 二分查找 - **题目示例**: - POJ 3373、POJ 1691:二分查找技术的...
ACM常用算法及其相应的练习题 本资源总结了 ACM 竞赛中常用的算法和相应的练习题,涵盖了基础算法、图...* KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 * 搜索的技巧和优化 + poj3411, poj1724
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...
6. **KMP算法**: - (poj1961, poj2406):高效的字符串匹配算法。 ### 十、进阶状态压缩 1. **状态压缩技巧**: - 如何高效地表示和压缩状态。 2. **状态压缩优化**: - (poj3411, poj1724):进一步提高状态...
如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合...
3. KMP 算法(poj1961, poj2406) 4. 左偏树(可合并堆) 四、搜索 1. 最优化剪枝和可行性剪枝 2. 较为复杂的动态规划(如动态规划解特别的施行商问题等) 3. 记录状态的动态规划 4. 树型动态规划 五、计算几何学...
- **应用场景**: 测试对算法的理解和实现能力。 - **示例题目**: POJ 3393, POJ 1472, POJ 3371, POJ 1027, POJ 2706 - **注意事项**: 细致地分析题目需求。 #### 二、图算法 **1. 差分约束系统** - **定义**:...
7. **字符串处理**:KMP算法、Rabin-Karp算法、Manacher's Algorithm等。 8. **模拟法**:按照题目描述进行程序设计,模拟实际情况。 9. **编码技巧**:如位操作、动态类型、模板等,以提高代码效率或简洁性。 ...
7. **数学**:poj1286、poj2409等继续深入组合数学,poj1226、poj1961等训练了KMP算法,poj3440、poj3071等涉及概率问题和高斯消元法。 这个训练计划通过精心挑选的题目,逐步提升编程者的算法思维和实现能力,为...
4. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法等字符串匹配方法,以及字符串操作(子串查找、模式匹配、字符串反转等)。 5. **编码技巧**:IO流的高效处理(缓冲区读写、文件流、字符编码等)、位...
2. **POJ1790**:可能涉及字符串的模式匹配,如KMP算法或Boyer-Moore算法,用于在一个字符串中寻找另一个字符串的出现位置。 3. **POJ1951**:可能与字符串的排序有关,比如可以运用Manacher's Algorithm解决最长...
- 字符串匹配算法如KMP算法可以提高字符串匹配的效率。 以上列举的题目只是冰山一角,POJ上还有更多类型的题目等待着大家去探索。通过不断练习这些题目,可以逐渐建立起解决各类问题的能力,为参加更高级别的竞赛...
5. **字符串处理**:KMP算法、Boyer-Moore算法、Rabin-Karp算法等字符串匹配方法。 6. **位运算**:利用位运算进行高效计算,如快速幂、异或操作等。 7. **优化技巧**:如代码优化、内存管理、预处理指令、递归...