Ile różnych wspólnych podsłów mają dwa ciągi?

Question

Takie zadanie: Neon

Próbowałem robić algorytmy na kształt LCS, ale nie wiem w jaki sposób wykrywać i zliczać podciągi które są np dwuliterowe, mógłby mi ktoś dać jakąś podpowiedź :D

Answer 1

Trochę mi to zajeło, ale mam rozwiązanie. To ogólnie pomysł jest podobny jak przy liczeniu ilości podsłów. Tylko będzie mała różnica dla przypadku, gdy A[i] == B[j], gdzie A i B to te słowa z wejścia. 

Powiedzmy, że dp[i][j] to ilość różnych podsłów dla słów A[0..i-1] i B[0..j-1]. Teraz liczymi dp[i][j] i A[i-1] == B[j-1]. Mamy dwa przypadki:

1) Nie dodajemy litery A[i-1] na koniec podsłowa, czyli szukamy ilości różnych podsłów tylko dla słów A[0...i-2] i B[0...j-2]. Tę liczbę znamy, bo wynosi dp[i-1][j-1]

2) Dodajemy A[i-1] na koniec podsłów. Czyli szukane podsłowo musi zakończyć się literą A[i-1] i musimy znać ilość różnych podsłów dla słów A[0...i-2] i B[0...j-2], a ta wartość znowu wynosi dp[i-1][j-1]. Teraz tylko pojawia się problem. Co jeżeli w A[0..i-2] i B[0..j-2] pojawiły się już kiedyś litery A[i-1]? A no policzymy jakieś duplikaty, czyli musimy coś odjąć od dp[i][j]. Wartość którą odejmiemy będzie dp[lastA(i-1)][lastB(j-1)], gdzie lastA(i) to ostatnia pozycja przed i w słowie A, dla której A[lastA(i)] = A[i], analogicznie działa lastB(i). Jeżeli A[i] lub B[j] jest pierwszym wystąpieniem danej litery to nic nie odejmujemy. Ogólnie musimy to odjąć, bo jakby jeżeli mamy jakieś podsłowo i występuje w nim litera z pozycji lastA(i). To możemy ją zastąpić literą A[i] i to utworzy to samo podsłowo.

Jeżeli A[i-1] != B[j-1] to robimy tak samo jak w algorytmie na liczenie ilości podsłów.

Kod wygląda jakoś tak:

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

const long long MOD = 1e9+9;
 
int calc(string& A, string& B)
{                                 
    vector<vector<long long> > dp(A.length() + 1, vector<long long>(B.length() + 1, 0));
    vector<int> lastA(A.length(), -1), lastB(B.length(), -1), last(30, -1);

    for(int i = 0; i < A.length(); i++)
    {
        lastA[i] = last[A[i]-'a'];
        last[A[i]-'a'] = i;
    }

    fill(begin(last), end(last), -1);
    for(int i = 0; i < B.length(); i++)
    {
        lastB[i] = last[B[i]-'a'];
        last[B[i]-'a'] = i;
    }
 
    for (int i = 1; i <= A.length(); i++)
    {                                    
        for (int j = 1; j <= B.length(); j++)
        {                                 
            if (A[i-1] == B[j-1])                                              
            {
                dp[i][j] = 2*dp[i-1][j-1];

                if(lastA[i-1] == -1 || lastB[j-1] == -1)
                    dp[i][j]++;

                if(lastA[i-1] != -1 && lastB[j-1] != -1)
                    dp[i][j] -= dp[lastA[i-1]][lastB[j-1]];
            }

            else                                                               
                dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];      

            dp[i][j] = (dp[i][j]+10LL*MOD)%MOD;               
        }                                                                       
    }
 
    return dp[A.length()][B.length()];
}                                                                               
 
int main()
{                                                                     
    ios::sync_with_stdio(0);                                                    
    cin.tie(nullptr);                                                              
 
    int n, m;
    string A, B;

    cin >> n >> m;
    cin >> A >> B;

    cout << calc(A, B) << '\n';
}