반응형
https://www.acmicpc.net/problem/4354
4354번: 문자열 제곱
알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다
www.acmicpc.net
알고리즘
s = a^n을 만족하는 가장 큰 n을 찾는다는 것은 문자열의 패턴의 최대 갯수를 찾으라는 문제다. 주의해야 할 점은 문자열의 최대 길이는 백만글자 미만이다. 인덱스별 탐색을 하려면 O(n^2)으로 시간초과가 날 것이다. 즉, 문자열 비교를 효율적으로 탐색하기 위해 KMP 알고리즘을 사용해야 한다.
KMP 알고리즘이란? https://sasca37.tistory.com/134
[Algorithm] KMP 알고리즘
KMP 알고리즘 KMP는 알고리즘을 설계한 Knuth-Morris-Pratt의 앞글자를 하나씩 따서 만든 알고리즘으로 문자열 검색을 효율적으로 할 수 있는 알고리즘이다. (ctrl + f 해서 찾는 검색 알고리즘이 KMP 알고
sasca37.tistory.com
주어진 문자열마다 실패함수(가장 긴 부분 문자열)pi 배열을 만들어서 배열의 마지막 인덱스에서 가져온 패턴과 비교를 해준다. 실패 함수는 각 인덱스별로 비교하며, 실패를 하기 직전의 가장 긴 부분 문자열까지 넘어가서 인덱스를 비교하기 때문에 효율적으로 탐색할 수 있다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
while (true) {
String word = br.readLine();
if (word.equals(".")) break;
int[] pi = getPi(word);
// 비교할 인덱스
int indexCnt = word.length() - pi[word.length()-1];
// 비교할 인덱스랑 나누어 떨어지지 않는다면 패턴이 없으므로 1
if (word.length() % indexCnt != 0) sb.append("1").append("\n");
// 패턴 만큼 전체 길이에서 나눈다.
else sb.append(word.length() / indexCnt).append("\n");
}
System.out.println(sb);
}
private static int[] getPi(String word) {
int[] pi = new int[word.length()];
int j = 0;
for (int i=1; i<pi.length; i++) {
// 직전에 일치한 인덱스가 있었으나, 그 다음에 인덱스가 다를 경우 직전 실패함수 값으로 돌아감
while (j > 0 && word.charAt(i) != word.charAt(j)) {
j = pi[j-1];
}
// 비교하는 인덱스가 같다면 pi에 j를 증가시켜 집어넣는다.
if (word.charAt(i) == word.charAt(j)) pi[i] = ++j;
}
return pi;
}
}
반응형
