글 읽기 - 최대 문자열 붙이기, 메모리 초과가 왜 뜨는거죠??:;; C++

museum114 4년 전 0

재귀호출도 없고 배열 크기도 과하지 않은데 메모리 초과가 뜨는 이유를 전혀 모르겠습니다;;

/* 최대 문자열 붙여넣기 */

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

#define ATTACH 1
#define DETACH 0
#define MAX_N 505
#define MAX_L 100005

using namespace std;

vector<vector<int>> can_str;
vector<int> pi;
string main_str;
string sub_str[MAX_N];
int Dp[MAX_L];
int Ans, N_of_short, Main_size;

void getpi(int);
void kmp(int index);
void dynamic();

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> main_str >> N_of_short;
    Main_size = (int)main_str.size();
    can_str.resize(Main_size);

    for (int i = 0; i < N_of_short; i++) 
        cin >> sub_str[i];

    for (int i = 0; i < N_of_short; i++) {
        getpi(i);
        kmp(i);
    }
  
    dynamic();
    cout << Ans;
    return 0;
}

void getpi(int index) {
    pi.resize((int)sub_str[index].size(), 0);

    for (int i = 1, j = 0; i < (int)sub_str[index].size(); i++) {
        while (j > 0 && (sub_str[index][i] != sub_str[index][j]))
            j = pi[j - 1];
        if (sub_str[index][i] == sub_str[index][j]) {
            pi[i] = ++j;
        }
    }
}

void kmp(int index) {
    for (int i = 0, j = 0; i < Main_size; i++) {
        while (j > 0 && main_str[i] != sub_str[index][j])
            j = pi[j - 1];
        if (main_str[i] == sub_str[index][j]) {
            if (j == ((int)sub_str[index].size() - 1)) {
                can_str[i - j].push_back(i);
                j = pi[j];
            }
            else
                ++j;
        }
    }
}

void dynamic() {
    int maxi = 0;
    for (int j = 0; j < (int)can_str[0].size(); j++) 
        Dp[can_str[0][j]] = can_str[0][j] - j + 1;    
    
    maxi = Dp[0];

    for (int i = 1; i < Main_size; i++) {
        for (int j = 0; j < (int)can_str[i].size(); j++) {
            int t = can_str[i][j];
            Dp[t] = max(Dp[t], maxi + t - i + 1);
            Ans = max(Dp[t], Ans);
        }
        maxi = max(maxi, Dp[i]);
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

최대 문자열 붙이기, 메모리 초과가 왜 뜨는거죠??:;; C++

museum114 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말