백준 4354 문자열 제곱

문제 링크 : https://www.acmicpc.net/problem/4354

※선행해야 할 알고리즘 : KMP Algorithm

1. 백준 1701문제(https://kuklife.tistory.com/2?category=797825)에서 pattern table을 구하는 방법을 적어놓았기에 이 부분은 생략하겠음.

2. 다음 예제 입력 문자열들의 patterntable값을 구하면 다음과 같다.

string	patterntable[string.size()-1]
abcd	0
aaaa	3
ababab	4

하지만, 문제가 원하는 값은 패턴 문자열들의 개수를 구하는 것임으로 다음과 같다.

string	패턴 문자열	패턴 문자열의 개수
abcd	abcd	1
aaaa	a	4
ababab	ab	3

첫번째와 두번째는 패턴 문자열이 없거나 1개밖에 없으니, 세번째 입력 예제를 통해 이해하기 바란다.

세번째 입력 예제에서 ab문자열이 패턴을 가지고 있다는 것을 파악하기 위해서는 패턴문자열이 몇 개의 문자를 가지고 있는지 알아야한다.

패턴 문자열의 문자 개수는 have_char라 칭하면 heve_char를 구하는 방법은 다음과 같다.(ababab)

 have_char = 문자열 길이 - patterntable[문자열 길이-1]

패턴 문자열의 문자 개수를 알았으면 해당 패턴 문자열의 개수를 구하는 방법은 쉽다. 전체 문자열를 have_char로 나누어주면 주면 된다.

즉, max_data = 문자열 길이 - have_char가 되는 것이다.

3. 이것을 계산해야 될 문자열의 개수인 k번 반복한 소스코드는 다음과 같다.

//kuklife.tistory.com #include<iostream> #include<vector> #include<string> using namespace std; vector<int> maxdata(vector<string> s) { vector<int>max_data(s.size(), 0); for (int k = 0; k < s.size(); k++) { vector<int>table(s[k].size(), 0); int j = 0, count = 0; for (int i = 1; i < s[k].size(); i++) { while (j > 0 && s[k][i] != s[k][j]) j = table[j - 1]; if (s[k][i] == s[k][j]) table[i] = ++j; } max_data[k] = s[k].size() / (s[k].size() - table[s[k].size() - 1]); } return max_data; } int main() { vector<string> s; string temp; for( ; ; ) { cin >> temp; if (!temp.compare(".")) break; else s.push_back(temp); } auto p = maxdata(s); for (int i = 0; i < p.size(); i++) cout << p[i] << endl; return 0; }