Cod sursa(job #2374727)

Utilizator AlexAxeToporan Victor AlexAxe Data 7 martie 2019 20:11:55
Problema Subsir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("subsir.in");
ofstream out("subsir.out");

const int NMax = 505, MOD = 666013;
short int N, M, DP[NMax][NMax], Sol;
char A[NMax], B[NMax];

void Read(){
    in >> A >> B;
    N = strlen(A);
    M = strlen(B);
}

void Solve(){
    int MaxLen = 0;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= M; ++j){
            if (A[i] == B[j]){
                if (i == 1 || j == 1)
                    DP[i][j] = 1;
                else
                    DP[i][j] = DP[i-1][j-1] + 1;
                if (DP[i][j] > MaxLen){
                    MaxLen = DP[i][j];
                    Sol = 1;
                }
                else if (DP[i][j] == MaxLen)
                    Sol++;
            }
            else
                DP[i][j] = 0;
        }
    out << Sol << '\n';
}

int main(){
    Read();
    Solve();
    return 0;
}