์ํ๋ฒณ ์๋ฌธ์๋ก ์ด๋ฃจ์ด์ง ๋ ๋ฌธ์์ด a์ b๊ฐ ์ฃผ์ด์ก์ ๋, ab๋ ๋ ๋ฌธ์์ด์ ์ด์ด๋ถ์ด๋ ๊ฒ์ ๋ปํ๋ค. ์๋ฅผ ๋ค์ด, a="abc", b="def"์ผ ๋, ab="abcdef"์ด๋ค.
์ด๋ฌํ ์ด์ด ๋ถ์ด๋ ๊ฒ์ ๊ณฑ์ ์ผ๋ก ์๊ฐํ๋ค๋ฉด, ์์ด ์๋ ์ ์์ ์ ๊ณฑ๋ ์ ์ํ ์ ์๋ค.
a^0 = "" (๋น ๋ฌธ์์ด)
a^(n+1) = a*(a^n)
๋ฌธ์์ด s๊ฐ ์ฃผ์ด์ก์ ๋, ์ด๋ค ๋ฌธ์์ด a์ ๋ํด์ s=a^n์ ๋ง์กฑํ๋ ๊ฐ์ฅ ํฐ n์ ์ฐพ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ ๋ ฅ์ 10๊ฐ ์ดํ์ ํ ์คํธ ์ผ์ด์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. ๊ฐ๊ฐ์ ํ ์คํธ ์ผ์ด์ค๋ s๋ฅผ ํฌํจํ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๋ค. s์ ๊ธธ์ด๋ ์ ์ด๋ 1์ด๋ฉฐ, ๋ฐฑ๋ง๊ธ์๋ฅผ ๋์ง ์๋๋ค. ๋ง์ง๋ง ํ ์คํธ ์ผ์ด์ค์ ๋ค์ ์ค์ ๋ง์นจํ์ด๋ค.
์ถ๋ ฅ
๊ฐ๊ฐ์ ํ ์คํธ ์ผ์ด์ค์ ๋ํด, s=a^n์ ๋ง์กฑํ๋ ๊ฐ์ฅ ํฐ n์ ์ฐพ์ ๋ค ์ถ๋ ฅํ๋ค.
๐ก ์คํจ ํจ์ ์ด์ฉํ์ฌ ๋ฐ๋ณต๋๋ ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํจ
๐ก ๋ฐ๋ณต๋์ง ์์ผ๋ฉด 1์ ์ถ๋ ฅํ๊ณ , ๋ฐ๋ณต๋๋ ๋ฌธ์์ด์ด๋ผ๋ฉด ๋ฐ๋ณต๋๋ ์ต์ ๋ฌธ์์ด์ ๊ธธ์ด๋ฅผ ๊ตฌํจ
static void getPi(String pattern) {
char[] p = pattern.toCharArray();
int j = 0;
for(int i=1; i<p.length; i++) {
while(j>0 && p[i] != p[j]) {
j = pi[j-1];
}
if(p[i] == p[j]) {
pi[i] = ++j;
}
}
}
int last = pi[len-1];
if(len%(len-last) != 0)
System.out.println(1);
else
System.out.println(len / (len - last));
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Imple_16 {
static int[] pi;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
String s = br.readLine();
if(s.equals("."))
return;
int len = s.length();
pi = new int[len];
getPi(s);
int last = pi[len-1];
if(len%(len-last) != 0)
System.out.println(1);
else
System.out.println(len / (len - last));
}
}
static void getPi(String pattern) {
char[] p = pattern.toCharArray();
int j = 0;
for(int i=1; i<p.length; i++) {
while(j>0 && p[i] != p[j]) {
j = pi[j-1];
}
if(p[i] == p[j]) {
pi[i] = ++j;
}
}
}
}
์ฑ๊ณตโจ