题目地址: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;
}
}
分享到:
相关推荐
POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看 POJ各题算法分类和题目推荐 ACM必看
#include using namespace std;...bool kmp(char *t,char *p) { int i,j; for(i=lenp,j=0;i;i++) { if(t[i]!=p[j]) return false; if(t[i]==p[j]) j++; if(j==lenp) j=0; } return true; }
poj1087贪心算法实验报告 poj1087贪心算法实验报告
POJ中级图算法所有题目【解题报告+AC代码】 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj acm题解,包括绝大部分poj题目的题解,可以供acm爱好者学习研究
POJ各题算法分类和题目推荐.pdf
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
供初学编程基本算法的人练习使用,在poj.grids.cn上
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ初级-图算法 解题报告+AC代码
北大POJ初级-基本算法 解题报告+AC代码
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
北大POJ中级-基本算法 解题报告+AC代码
关于C++ 算法 北大网站POJ 八数码问题
用贪心算法解决POJ 1065的木棍处理问题
这里面有介绍ACM中的算法,包括算法分类,以及对应在POJ上面的训练题目
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为: