palindromize 팰린드롬 만들기 kmp 시간초과

  • ckdhyeon95
    ckdhyeon95

    나름대로 kmp 알고리즘을 이용하여 문제를 해결하려고 했으나 시간초과가 떴습니다.
    kmp의 경우 빅오가 선형시간복잡도로 알고있는데 제 코드에서 시간초과가 뜬 이유가 무엇인지 알고싶습니다.
    감사합니다.

    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    
    using namespace std;
    
    int getPartialMatch(const string& is, const string& rs) {
    
        int len = is.size();
    
        int begin = 0;
        int matched = 0;
    
        vector<int> piVec(len, 0);
        while (begin + matched < len) {
    
            if (is[begin + matched] == rs[matched]) {
                matched += 1;
                piVec[begin + matched - 1] = matched;
            }
    
            else if (matched == 0)
                begin += 1;
    
            else {
                begin += matched - piVec[matched - 1];
                matched = piVec[matched - 1];
            }
    
        }
    
        return piVec[len - 1];
    
    }
    
    int main() {
    
        int testCase;
        cin >> testCase;
        while (testCase-- > 0) {
    
            string inputStr;
            cin >> inputStr;
    
            string reverseStr = inputStr;
            reverse(reverseStr.begin(), reverseStr.end());
    
            int overlap = getPartialMatch(inputStr, reverseStr);
    
            cout << inputStr.size() * 2 - overlap << '\n';
    
        }
    
        return 0;
    }
    

    1달 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.