# AISD LISTA 3

Podpunkty a i b są wspólne. W a) zwracamy LIS[n][m][6],
w b) max(LIS[n][m][0-5])


liczby poza tablicą dp[n][m][k] np dp[0][-1][2] są równe zero
char znak[]{null,m,a,t,u,r,a}
for (i in range(n)) { // iteracja "w dół"
    for (j in range(m)) { // iteracja "w prawo"
        for (k in range(7)) { // iteracja po tablicach -> "literkach"
            dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k])

            if(s1[i] == s2[j]) {
                if (s1[i] == znak[k]) {
                    dp[i][j][k] = max(dp[i-1][j-1][k-1] + 1, dp[i][j][k])
                }                
                else {
                     dp[i][j][k] = max(dp[i-1][j-1][k] + 1, dp[i][j][k])
                }
            }
        }      
    }      
}

Podpunkty c i d również wspólnie - zwrócimy wartość jak w a) i b) (analogicznie):

dp[n][m][k] oznacza najdłuższy wspólny podciąg dla 2 prefixów, że zawiera dokładnie k pierwszych liter "matura" na samym końcu, lub (w przypadku 6) kiedykolwiek w środku zawierał całe słowo "matura"



char znak[]{null,m,a,t,u,r,a}
for (i in range(n)) { // iteracja "w dół"
    for (j in range(m)) { // iteracja "w prawo"
        for (k in range(7)) { // iteracja po tablicach -> "literkach"
            dp[i][j][k] = max(dp[i][j-1][k], dp[i-1][j][k])
            
            if (k == 0) {
                 for (other_k in range(6)) { // other_k -> 3, znak[other_k + 1] = "u", s1[i]= "p"
                     if (s1[i] == s2[j] !== znak[other_k + 1]) {
                         dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][other_k] + 1)
                     }
 
                 }
            }     
            
            else if (k == 6) {
                if (s1[i] == s2[j] == znak[k]) {
                    dp[i][j][k] = max(dp[i-1][j-1][k-1] + 1, dp[i][j][k])
                }                
                if (s1[i] == s2[j]) {
                    dp[i][j][k] = max(dp[i-1][j-1][k] + 1, dp[i][j][k])
                }
            }          
            
            else {
                if (s1[i] == s2[j] == znak[k]) {
                    dp[i][j][k] = max(dp[i-1][j-1][k-1] + 1, dp[i][j][k])
                } 
            }
        }
    }
}

## MW C++
### a,b

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e1 + 7;
constexpr int INF = 1e9;

int dp[MAXN][MAXN][7];
int n, m, mSize;

void initDp() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j][0] = 0;
            for (int k = 1; k <= mSize; k++) {
                dp[i][j][k] = -INF;
            }
        }
    }
}
int main() {
    string matura = "matura";
    string x = "mabtursafe";
    string y = "maturasa";
    mSize = matura.size();

    n = x.size();
    m = y.size();

    x = "$" + x;
    y = "$" + y;
    matura = "$" + matura + "$";

    initDp();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= mSize; k++) {
                dp[i][j][k] = max(dp[i - 1][j][k], dp[i][j - 1][k]);

                if (x[i] == y[j]) {
                    if (x[i] == matura[k]) {
                        dp[i][j][k] = max(dp[i - 1][j - 1][k - 1] + 1, dp[i][j][k]);
                    } else if (x[i] != matura[k + 1]) {
                        dp[i][j][k] = max(dp[i - 1][j - 1][k] + 1, dp[i][j][k]);
                    }
                }
            }
        }
    }

    cout << "A:" << dp[n][m][mSize] << endl;
    int mx = 0;

    for (int i = 0; i < mSize; i++) {
        mx = max(dp[n][m][i], mx);
    }

    cout << "B:" << mx << endl;
}

### c, d

#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 1e1 + 7;
constexpr int INF = 1e9;

int dp[MAXN][MAXN][7];
int n, m, mSize;

void initDp() {
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            dp[i][j][0] = 0;
            for (int k = 1; k <= mSize; k++) {
                dp[i][j][k] = -INF;
            }
        }
    }
}
int main() {
    string matura = "mt";
    string x = "mbtu";
    string y = "mtu";
    mSize = matura.size();

    n = x.size();
    m = y.size();

    x = "$" + x;
    y = "$" + y;
    matura = "$" + matura + "$";

    initDp();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int k = 0; k <= mSize; k++) {
                dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);

                if (k == 0) {
                    for (int other_k = 0; other_k < mSize; other_k++) {
                        if (x[i] == y[j] && y[j] != matura[other_k + 1]) {
                            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j - 1][other_k] + 1);
                        }
                    }
                    continue;
                }

                // k != 0
                if (x[i] == y[j] && y[j] == matura[k]) {
                    dp[i][j][k] = max(dp[i - 1][j - 1][k - 1] + 1, dp[i][j][k]);
                }
                if (k == mSize) {
                    if (x[i] == y[j] && x[i] != matura[k + 1]) {
                        dp[i][j][k] = max(dp[i - 1][j - 1][k] + 1, dp[i][j][k]);
                    }
                }
            }
        }
    }

    cout << "C:" << dp[n][m][mSize] << endl;
    int mx = 0;

    for (int i = 0; i < mSize; i++) {
        mx = max(dp[n][m][i], mx);
    }

    cout << "D:" << mx << endl;
}