[11585번] 속타는 저녁 메뉴

문제 출처 :

https://www.acmicpc.net/problem/11585

알고리즘 분석 :

문제 해결에 필요한 사항

1. KMP

KMP 알고리즘을 이용하여 문제를 풀 수 있다.

이 문제는 결국 3번째줄 문자열이 2번째줄의 문자열에서 몇 번 나오는지 묻고 있는 것과 같다.

따라서 2번째줄 문자열을 2배로( abc일때 abcabc로 ) 만들어주고 3번째줄 문자열과 kmp를 돌리면 최댓값을 알 수 있다.

이때 조심해야 할 점은 2번째줄이 abc, 세번째줄이 abc라면 abcabc와 abc를 kmp를 돌리게 되면 답이 2/3이 나오게 되기에 오답을 받을 수 있다.

따라서 abcabc를 만든 후 마지막 값은 빼주도록 하여 저러한 상황에서 오답이 나오지 않도록하자.

또한 하나 더 이야기를 해보자면 3번째줄의 문자열은 필요가 없다.

왜냐면 2번째줄과 3번째줄의 문자열은 항상 같은 값이기에 2번째줄의 문자열로만으로 해결 할 수 있다.

즉, AABAAB일때 AABAABAABAA와 AABAAB로 답을 구할 수 있다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78

#include <iostream> #include <cstdio> #include <string> #include <vector>   using namespace std; int gcd(int a, int b) { return !b ? a : gcd(b, a%b); }   char tmp[1000001];   vector<int> getPi(string p) {     int m = (int)p.size();     int j = 0;       vector<int> pi(m, 0);       for (int i = 1; i< m; i++) {         while (j > 0 && p[i] != p[j])             j = pi[j - 1];         if (p[i] == p[j])             pi[i] = ++j;     }     return pi; } vector<int> kmp(string s, string p) {     vector<int> ans;     auto pi = getPi(p);     int n = (int)s.size(), m = (int)p.size(), j = 0;     for (int i = 0; i < n; i++) {         while (j>0 && s[i] != p[j])             j = pi[j - 1];         if (s[i] == p[j]) {             if (j == m - 1) {                 ans.push_back(i - m + 1);                 j = pi[j];             }             else {                 j++;             }         }     }     return ans; }   int main() {     int n;     string s, p;       scanf("%d ", &n);     for (int i = 0; i < n; i++)         cin >> tmp[i];       p = tmp;     s = tmp;     s += s;       s.pop_back();       for (int i = 0; i < n; i++)         cin >> tmp[i];       vector<int> ans = kmp(s, p);       int a = ans.size();     int t = gcd(a, n);     a /= t;     n /= t;       cout << a << "/" << n << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus