算法训练 字串统计
时间限制: 1.0s 内存限制: 512.0MB
问题描述
给定一个长度为 n 的字符串 S, 还有一个数字 L, 统计长度大于等于 L 的出现次数最多的子串 (不同的出现可以相交), 如果有多个, 输出最长的, 如果仍然有多个, 输出第一次出现最早的.
输入格式
第一行一个数字 L.
第二行是字符串 S.
L 大于 0, 且不超过 S 的长度.
输出格式
一行, 题目要求的字符串.
输入样例 1:
4
bbaabbaaaaa
输出样例 1:
bbaa
输入样例 2:
2
bbaabbaaaaa
输出样例 2:
aa
数据规模和约定
n<=60
S 中所有字符都是小写英文字母.
提示
枚举所有可能的子串, 统计出现次数, 找出符合条件的那个
思路: 暴力!!!
- import java.util.Arrays;
- import java.util.Scanner;
- public class Main {
- public static void main(String[] args) {
- Scanner cin = new Scanner(System.in);
- String[] str = new String[3800];
- int n = cin.nextInt();
- String yuan = cin.next();
- int len = yuan.length();
- int ct = 0;
- for(int i = 0; i <len; i++) {
- for(int j = i; j < len; j++) { // i 和 j 的关系
- str[ct++] = yuan.substring(i, j+1);
- }
- }
- int[] cishu = new int[ct];
- // 哦统计
- for(int i = 0; i < ct; i++) {
- for(int j = 0; j < ct; j++) {
- if(i != j && str[i].equals(str[j])) {
- cishu[i]++;
- }
- }
- }
- int max = 0;
- String ans = ""; // 最长的串
- for(int i = 0; i < ct; i++) {
- if(str[i].length()>= n) {
- if(cishu[i]> max) {
- max = cishu[i];
- ans = str[i];
- }
- else if(cishu[i] == max) {
- if(str[i].length()> ans.length()) {
- max = cishu[i];
- ans = str[i];
- }
- }
- }
- }
- if(ans.length() == 0) {
- }
- else {
- System.out.println(ans);
- }
- }
- }
- //4
- //bbaabbaaaaa
来源: http://www.bubuko.com/infodetail-2964936.html