[백준] 2401 - 최대 문자열 붙여넣기 KMP + DP Cpp 코드

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

2401번: 최대 문자열 붙여넣기

#include <bits/stdc++.h>
using namespace std;
#define LEN_MAX 100003

string shortStr[501];
int lps[501][10001];
int mem[501];

int dp[LEN_MAX];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    string longStr;
    int n, Len;
    cin >> longStr >> n;
    Len = longStr.length();

    //BFS 좌표 저장
    for(int N=0; N<n; N++){
        cin >> shortStr[N];

        int sLen = shortStr[N].length();
        for(int i=1, j=0; i<sLen; i++){
            while(j>0 && shortStr[N][i]!=shortStr[N][j]){
                j = lps[N][j-1];
            }
            if(shortStr[N][i]==shortStr[N][j]){
                lps[N][i] = ++j;
            }
        }
    }

    
    
    for(int i=0; i<Len; i++){
        if(i>0) dp[i] = dp[i-1];

        for(int j=0; j<n; j++){
            int sLen = shortStr[j].length();

            while(mem[j]>0 && longStr[i]!=shortStr[j][mem[j]]){
                mem[j] = lps[j][mem[j] - 1];
            }

            if(longStr[i]==shortStr[j][mem[j]]){
                if(mem[j] == sLen - 1){
                    //dp[-1] 방 지
                    int tmp = i -sLen >= 0 ? dp[i-sLen] : 0;
                    tmp += sLen;
                    dp[i] = max(dp[i], tmp);

                    mem[j] = lps[j][mem[j]];
                }
                else{
                    mem[j]++;
                }
            }

        }
    }

    cout << dp[Len-1] << '\n';

    return 0;
}