Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1041
A newly opened detective agency is struggling with their limited intelligence to find out a secret information passing technique among its detectives. Since they are new in this profession, they know well that their messages will easily be trapped and hence modified by other groups. They want to guess the intensions of other groups by checking the changed sections of messages. First they have to get the length of longest match. You are going to help them. Input The input file may contain multiple test cases. Each case will contain two successive lines of string. Blank lines and non-letter printable punctuation characters may appear. Each Line of string will be no longer than 1000 characters. Length of each word will be less than 20 characters. Output For each case of input, you have to output a line starting with the case number right justified in a field width of two, followed by the longest match as shown in the sample output. In case of at least one blank line for each input output ‘Blank!’. Consider the non-letter punctuation characters as white-spaces. Sample Input This is a test. test Hello! The document provides late-breaking information late breaking.
Sample Output 1.
Length of longest match: 1 2. Blank! 3.
Length of longest match: 2
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int main()
{
string in1,in2;
int tc=1;
while(getline(cin,in1)){
getline(cin,in2);
cout << setw(2) << fixed << tc++ << ". ";
if(in1.empty() || in2.empty()){
cout << "Blank!" << endl;
continue;
}
in1 = regex_replace(in1,regex("[^a-zA-Z0-9]")," ");
in2 = regex_replace(in2,regex("[^a-zA-Z0-9]")," ");
vector < string> seqA, seqB;
istringstream iss(in1);
while(iss >> in1) seqA.push_back(in1);
iss.clear(); iss.str(in2);
while(iss >> in2) seqB.push_back(in2);
vector<int> dp(seqB.size()+1);
for(int i=0;i < seqA.size();i++){
vector<int> dpNext(seqB.size()+1);
for(int j=0;j i&It seqB.size();j++){
if(seqA[i] == seqB[j])
dpNext[j+1] = dp[j]+1;
else
dpNext[j+1] = max(dp[j+1],dpNext[j]);
}
dp = dpNext;
}
cout << "Length of longest match: " << dp.back() << endl;
}
} Input
test
Hello!
The document provides
late-breaking information
late breaking.
Output
2. Blank!
3. Length of longest match: 2
Demonstration
UVA Online Judge solution - 10100 - Longest Match - UVA Online Judge solution in C,C++,Java