It's Mooin' Time

시간 제한2초메모리 제한2048 MB

요약
길이 3인 moo 패턴 c_i c_j c_j가 최소 F번 나타나는 경우를 모두 찾되, 문자열에서 최대 한 글자까지 바꿀 수 있다.
난이도

보통10점 중 7점

유형
문자열, 해시맵, 문자열 매칭, 완전 탐색
정답자
아직 제출이 없습니다

문제

Farmer John is trying to describe his favorite USACO contest to Elsie, but she is having trouble understanding why he likes it so much. He says "My favorite part of the contest was when Bessie said 'It's Mooin' Time' and mooed all over the contest."

Elsie still doesn't understand so Farmer John downloads the contest as a text file and tries to explain what he means. The contest is defined as a string of lowercase letters of length NN (3≤N≤20,0003 \leq N \leq 20\\,000). A moo is generally defined as the substring c_ic_jc_jc\_ic\_jc\_j where some character c_ic\_i followed directly by 22 occurrences of some character c_jc\_j where c_i≠c_jc\_i \neq c\_j. According to Farmer John, Bessie moos a lot, so if some moo appears at least FF (1≤F≤N1\le F\le N) times in the contest, that might be from Bessie.

However, Farmer John's download might have been corrupted, and the text file might have up to one character that differs from the original file. Print all possible moos that Bessie could have made taking the potential error into account, sorted in alphabetical order.

입력

The first line contains NN and FF, representing the length of the string and the frequency threshold for a moo by Bessie.

The second line contains a string of lowercase letters of length NN, representing the contest.

출력

Print out the number of possible moos that Bessie makes, followed by a lexicographically sorted list of the moos. Each moo should appear on a separate line.

예제3

  1. 예제 1

    입력
    10 2
    zzmoozzmoo
    
    예상 출력
    1
    moo
    
  2. 예제 2

    입력
    17 2
    momoobaaaaaqqqcqq
    
    예상 출력
    3
    aqq
    baa
    cqq
    
  3. 예제 3

    입력
    3 1
    ooo
    
    예상 출력
    25
    aoo
    boo
    coo
    doo
    eoo
    foo
    goo
    hoo
    ioo
    joo
    koo
    loo
    moo
    noo
    poo
    qoo
    roo
    soo
    too
    uoo
    voo
    woo
    xoo
    yoo
    zoo