https://www.acmicpc.net/problem/1498
1498번: 주기문
어떤 문자열 X를 n번 연달아 쓴 것을 (X)^n으로 나타내기로 하자. 예를 들어 (ab)^3는 ababab를 의미한다. 어떤 문자열 Y가 (X)^n 꼴로 표현될 수 있다면, 그리고 n이 1이 아니라면 Y를 주기문 이라고 한다
www.acmicpc.net
실패함수의 응용의 응용
반복되는 가장 작은 문자열 == 문제에서 원하는 "주기문" 의 길이를
https://blog.koderpark.dev/263
백준 BOJ 1305 - 광고
@이화월백 이 골라준 태그 문제풀이 오늘의 태그는 KMP되시겠다 https://www.acmicpc.net/problem/1305 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있
blog.koderpark.dev
1305번의 아이디어에서 착안해서
$(N+1) - fail(N)$ 으로 구해줄 수 있으며,
X^n 꼴로 표현되는 가장 큰 수 K는
https://blog.koderpark.dev/264
백준 BOJ 4354 - 문자열 제곱
오늘의 KMP 그 두번째 문제 https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc"
blog.koderpark.dev
4354번의 아이디어에서 착안해 와서
구해줄 수 있다.
즉 문제에서 요구하고있는 "주기문"인지에 대한 판별을
문자열의 길이 $N+1$ 이 주기문의 길이 $(N+1) - fail(N)$ (앞으로 $len$ 이라 하겠다)
로 나누어떨어지는지를 통해서 확인해줄 수 있다.
이렇게 확인해준 뒤에 문자열의 길이 $N+1$ 과 $N+1/len$ 를 출력해주면 정답을 받을 수 있다.
#include<bits/stdc++.h>
using namespace std;
int fail[1234567] = {0};
int main(){
string s;
cin >> s;
int N = s.length();
for(int i=1,j=0; i<N; i++){
while(j && s[i] != s[j]) j = fail[j-1];
if(s[i] == s[j]) fail[i] = ++j;
}
for(int i=1; i<N; i++){
int len = (i+1)-fail[i];
if(fail[i] && (i+1)%len == 0){
printf("%d %d\n", (i+1),(i+1)/len);
}
}
return 0;
}오랜만에 kmp 잡아서 그런가 알?쏭달쏭한 문제였다
안한티가 팍팍나는군
반성을해야....
