Editorial for The Homework

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

English

This problem is a modified version of the Longest Common Substring problem. To solve this problem all we have to do is to implement a really basic dp model of sizes (wordCount(str1)\(\times\)wordCount(str2)). To solve the problem we will compare every word in str1 with every word within str2 and save this comparisons to the 2D matrix. If (a+1)th word in str1 and (b+1)th word in str2 are not the same we will set the [a+1][b+1]th entry of the dp array to 0. If they are the same we will set the [a+1][b+1] th entry of the 2D dp array to the [a][b]th entry of the dp array +1. This way the time complexity of the problem will become O(\(N^2\)) instead of the naive approach which would have been O(\(N^3\)).

Türkçe

Bu problem, Longest Common Substring probleminin değiştirilmiş bir halidir. Bu problemi çözmek için tek yapmamız gereken, (wordCount(str1)\(\times\)wordCount(str2)) boyutunda basit bir dp(dynamic programming) modeli uygulamaktır. Problemi çözmek için str1'deki her kelimeyi str2'deki her bir kelimeyle karşılaştıracağız ve bu karşılaştırmaları 2D matrixe kaydedeceğiz. str1'deki (a+1)'inci kelime ve str2'deki (b+1)'inci kelime aynı değilse, dp array'inin [a+1][b+1]'inci elemanını 0 olarak ayarlayacağız. Eğer aynılarsa, 2D dp array'inin [a+1][b+1]'inci elemanını, dp array'inin [a][b]'inci elemanı + 1 olarak ayarlayacağız. Bu şekilde, problemin zaman complexity'si, O(\(N^3\)) olan naive yaklaşım yerine O(\(N^2\)) olur.

Code C++

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

void createWordTable(vector<string> &);
void solve(){
    vector<string> vec1,vec2;
    createWordTable(vec1);
    createWordTable(vec2);

    int x,y;
    x=vec1.size();
    y=vec2.size();
    int arr[x][y];

    int BEST=0;

    for(int i=0;i<x;i++){
        if(vec1[i]==vec2[0]){
            arr[i][0]=1;
            BEST=1;
        }
        else arr[i][0]=0;
    }

    for(int i=0;i<y;i++){
        if(vec1[0]==vec2[i]){
            arr[0][i]=1;
            BEST=1;
        }
        else arr[0][i]=0;
    }

    for(int i=1;i<x;i++){
        for(int k=1;k<y;k++){
            if(vec1[i]==vec2[k]){
                arr[i][k]=arr[i-1][k-1]+1;
                if(arr[i][k]>BEST){
                    BEST++;
                }
            }
            else arr[i][k]=0;
        }
    }

    cout<<BEST<<endl;



}
int main(){
    int t;
    cin>>t;
    while(t--)solve();
}



void createWordTable(vector<string> &vec){
    char c='.';
    string s;

    while(c!='\n'){
        cin>>s;
        vec.push_back(s);
        c=getchar();
    }
}

Code Python

def lcs_with_words(s1, s2):
    p1 = s1.strip().split()
    p2 = s2.strip().split()

    m = len(p1)
    n = len(p2)

    dp = [[None for _ in range(n + 1)] for _ in range(m + 1)]
    BEST=0

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                dp[i][j] = 0
            elif p1[i - 1] == p2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
                if dp[i][j]>BEST:
                    BEST=dp[i][j]
            else:
                dp[i][j] = 0


    return BEST


N = int(input())

for _ in range(N):
    a = input()
    b = input()

    print(lcs_with_words(a, b))