백준 4354 (문자열 제곱)

문제

---

알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다.

이러한 이어 붙이는 것을 곱셈으로 생각한다면, 음이 아닌 정수의 제곱도 정의할 수 있다.

• a^0 = "" (빈 문자열)
• a^(n+1) = a*(a^n)

문자열 s가 주어졌을 때, 어떤 문자열 a에 대해서 s=a^n을 만족하는 가장 큰 n을 찾는 프로그램을 작성하시오.

 

 

 

풀이

---

 

2021.04.21 - [자료구조 공부/String] - 백준 1305 (광고)

백준 1305 (광고)

이 문제 또한 위 문제와 같이 반복패턴을 찾아가는 문제다.

 

이 문제에서는 두가지 경우가있다.

1. 찾아진 패턴이 반복되는 경우
2. 찾아진 패턴이 일부 반복되는 경우

1번의 경우는에는

S = a ^ n 의 경우 n 의 최대값을 찾을 수 있다.

 

하지만,

2번의 경우에는

S = a ^ 1 의 경우가 된다. 일부 반복된다는 것은 반복적인 패턴이 연속적으로 나오지 않는다는 것이기 때문에 하나의 패턴이라고 봐야한다.

 

따라서 Pi를 구해준 뒤 반복패턴으로 문자열이 나누어 떨어지는가 아닌가를 확인해서 값을 넣어주면 된다.

 

<전체코드>

import java.io.*;
import java.util.*;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		while(true) {
			String string = bufferedReader.readLine();
			
			if(string.equals("."))
				break;
			
			solve(string);
		}
		
		System.out.println(sb);
	}
	
	
	static void solve(String string) {
		
		int[] pi = new int[string.length()];
		
		int j = 0;
		for(int i = 1 ; i < string.length() ; i++) {
			
			while(j > 0 && string.charAt(i) != string.charAt(j)) {
				j = pi[j - 1];
			}
			
			if(string.charAt(i) == string.charAt(j)) {
				pi[i] = ++j;
			}
		}
		
		int patternLen = string.length() - pi[string.length() - 1];
		
		if( string.length() % patternLen == 0) {
			int n = string.length() / patternLen;
			sb.append(n + "\n");
		}
		else {
			sb.append("1\n");
		}

		return;
	}
}