https://algospot.com/judge/submission/recent/
알고리즘 문제 해결 전략 2의
20챕터에서 소개되는 문자열 관련 문제이다!
지난 학기 C프로그래밍 과제로 KMP 알고리즘이 나왔어서
어떤 알고리즘인지 알고 있었다
(과제 : https://www.acmicpc.net/problem/1786)
지난 번에 진짜 열심히 이해했는데
다시 보니까 하나도 모르겠는 거다?
그래서 이 분 글도 참고하고, 나동빈님 영상도 참고했다
https://gusdnd852.tistory.com/172
예전에도 이 분 글은 진짜 도움이 되었었다!
너무 정리를 잘해놓으셔서 까먹고 이해안될때마다 보면 좋을 것 같다
https://youtu.be/yWWbLrV4PZ8
이건 나동빈님 영상인데 내가 pi배열 직접 만들 때에는 생각지도 못한
우아한 방식으로 만들어내셔서 새로웠다!!!
근데 나는 아직 KMP 알고리즘 너무 어렵다 ㅜ
원래 문제 풀 때 초반에는 아무것도 참고하지 않는 편인데
이번에는 알고리즘 자체가 너무 복잡해서 알고리즘에 대한 참고를 많이 했다.
아직 KMP 알고리즘에 대한 이해가 완벽하지 않아서
정답이긴하지만 미해결 태그를 달아놓고 계속 찜찜해해야할 거 같다!ㅠ
CODE
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> GetPrefixSuffix(string & s);
vector<int> GetPiArray(string & s);
int main(void)
{
string mother;
string father;
cin>>father;
cin>>mother;
father.append(mother);
vector <int> result;
result = GetPrefixSuffix(father);
sort(result.begin(), result.end());
vector<int>:: iterator iter = result.begin();
for(iter = result.begin(); iter != result.end(); iter++)
{
cout<<*iter<<" ";
}
cout<<endl;
return 0;
}
// S의 접두사도 되고 접미사도 되는 모든 문자열의 길이 계산
// 1. pi[k]의 가장 큰 수를 찾는다.
// 2. 결과 배열에 넣는다
// 3. pi[k]의 값보다 -1한 값을 인덱스로 하는 pi[k]의 위치를 확인한다
// 4. 결과 배열에 넣는다
// - k가 0보다 크면 위 3,4과정을 반복한다
vector<int> GetPrefixSuffix(string & s)
{
int k = s.size();
vector<int> pi(k);
vector<int> resultArr;
pi = GetPiArray(s);
while(k > 0)
{
resultArr.push_back(k);
k = pi[k-1];
}
return resultArr;
}
vector<int> GetPiArray(string & s)
{
int j=0;
bool replay = false;
vector<int> piArr(s.size());
piArr.push_back(0);
for(int i=1; i<s.size(); i++)
{
if(replay)
{
i--;
replay = false;
}
if(s[i] != s[j])
{
piArr[i] = 0;
if(j > 0)
{
j = 0;
replay = true;
}
}
else
{
piArr[i] = j+1;
j++;
}
}
return piArr;
}아래는 pi배열의 구현 변천사이다
1. 내가 백준 과제를 위해 구현했던 pi배열 찾기 함수
세상 이렇게 복잡할 수가 없다 ㅋㅋ
// SetPiTable()
// 이 함수는 모든 P에 대한 k를 미리 계산해놓는 것이 목적
void SetPiTable(char *pattern, int pi[])
{
int i, j, k;
int len = strlen(pattern);
int check = 0, count = 0, end = 0;
// 접두사는 앞에서부터 읽고, 접미사는 뒤에서부터 읽는데 매 길이의 첫 글자부터 읽는다.
// ex) abaab이면, (접두사, 접미사는 자신의 문자열 길이보다 최소 1이라도 짧아야 함)
// prefix = { a, ab, aba, abaa }
// suffix = { b, ab, aab, baab }
// 위에 껄 i마다 반복해야 함
for (i = 0; i < len; i++)
{
for (j = 0; j < i; j++)
{
end = i - j; // 뒤에서부터 읽는데 매 길이의 첫 글자부터 읽도록 인덱스 설정
for (k = 0; k < j + 1; k++)
{
// 접두사와 접미사의 일치하는 개수를 찾는다
if (pattern[k] == pattern[end++]) // 일치하면
{
count++; // 카운트 증가
}
else // 일치하지 않으면
{
count = 0; // 카운트 초기화
break;
}
}
// count = 0이 되지 않고 내려왔을 경우 전부 다 일치한다는 것
if (count > check) // 겹치는 것 중 최댓값
check = count;
if (check > pi[i]) // pi값으로 설정
pi[i] = check;
count = 0;
}
check = 0;
count = 0;
}
}- 이건 나동빈님의 영상에서 배운 알고리즘을 참고해서 구현한 pi배열 찾기 함수
< 스케치 >
CODE
vector<int> GetPiArray(string & s)
{
int j=0;
bool replay = false;
vector<int> piArr(s.size());
piArr.push_back(0);
for(int i=1; i<s.size(); i++)
{
if(replay)
{
i--;
replay = false;
}
if(s[i] != s[j])
{
piArr[i] = 0;
if(j > 0)
{
j = 0;
replay = true;
}
}
else
{
piArr[i] = j+1;
j++;
}
}
return piArr;
}실제 나동빈님이 구현하신 코드는 이것보다 더 짧고 간결하다 (무한 존경)
이 사진은 내가 vector를 잘못사용해서 발생하는 문제였다
똑같은 코드임에도 불구하고 결과값이 출력될 때도 있고,
출력되지 않을 때도 있다.
원인은 내가 vector를 사용할 때 크기 지정을 안한 상태에서
인덱스로 접근을 하려고 해서 그런 것 같다
vector 선언부에 크기 지정을 해주었더니 해결이 되었다
앞으로 vector를 사용할 때 가능하다면 크기 지정을 해주고,
초기화해 준 다음 사용하는 것이 좋을 것 같다!
