package com.liuzhen.systemExe;

import java.util.Scanner;

public class Main{
    //KMP算法求取next函数值
    public int[] getNext(char[] array) {
        int[] next = new int[array.length + 1];
        int j = 0;
        for(int i = 1;i < array.length;i++) {
            while(j > 0 && array[i] != array[j]) {
                j = next[j];
            }
            if(array[i] == array[j]) {
                j++;
            }
            next[i + 1] = j;
        }
        return next;
    }
    //使用KMP算法求取arrayB子串在arrayA中符合匹配的个数
    public int getKmpCount(char[] arrayA, char[] arrayB) {
        int count = 0;
        int[] next = getNext(arrayB);
        int j = 0;
        for(int i = 0;i < arrayA.length;i++) {
            while(j > 0 && arrayA[i] != arrayB[j]) {
                j = next[j];
            }
            if(arrayA[i] == arrayB[j])
                j++;
            if(j == arrayB.length) {
                count++;
                i = i - j + 1;   //此处是因为题目中说：不同的出现可以相交
                j = 0;    
            }
        }
        return count;
    }
    //获取arrayA的开始位置为start长度L的子串
    public char[] getPartString(char[] arrayA, int start, int L) {
        char[] result = new char[L];
        int i = 0;
        while(i < L) {
            result[i++] = arrayA[start++]; 
        }
        return result;
    }
    //打印符合题意的子串
    public void printResult(String A, int L) {
        if(L <= 0 || L > A.length() || A.length() > 60 || A.equals(null))
            return;
        char[] arrayA = A.toCharArray();
        char[] max = getPartString(arrayA, 0, L);
        int maxCount = 1;
        while(L < arrayA.length) {
            for(int start = 0;start < arrayA.length - L;start++) {
                char[] partA = getPartString(arrayA, start, L);
                int tempCount = getKmpCount(arrayA, partA);
                if(tempCount > maxCount || (tempCount == maxCount && partA.length > max.length)) {
                    maxCount = tempCount;
                    max = partA;
                }
            }
            L++;
        }
        System.out.println(max);
    }
    
    public static void main(String[] args){
        Main test = new Main(); 
        Scanner in = new Scanner(System.in);
    //    System.out.println("请输入一个整数L和一个字符串A：");
        int L = in.nextInt();
        in.nextLine();
        String A = in.nextLine();
        test.printResult(A, L);
    }
}

请输入一个整数L和一个字符串A：
5
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba
baabaa