[URI Online Judge] – 1237 – Compare Substring

Find the longest common substring between the two informed Strings. The substring can be any part of the String, including the entire String. If there is no common substring, return 0. The search is case sensitive (‘x’ != ‘X’).

Input

The input contains several test cases. Each test case is composed by two lines that contains a string each. Both input Strings will contain between 1 and 50, inclusive, letters (a-z, A-Z), and/or spaces.

Output

The length of the longest common substring between the two Strings.

Sample Input Sample Output
abcdef
cdofhij
TWO
FOUR
abracadabra
open
Hey This java is hot
Java is a new paradigm
2
1
0
7

my solution:


#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstring>

using namespace std;

int count_substrings (char *str1, char *str2) {
int n1 = strlen(str1), n2 = strlen(str2);
int max = 0;

for (int i = 0; i < n1; i++) {
for (int j = 0; j < n2; j++) {
if (str1[i] == str2[j]) {
int c = 0;
for (int k = 0; k+i<n1, k+j<n2; k++) {
if (str1[k+i] != str2[k+j])
break;
c++;
}
if (c > max)
max = c;
}
}
}
return max;
}

int main () {
char str1[100], str2[100];

cin.getline(str1, 100);
while (cin.getline(str2, 100)) {
cout << count_substrings(str1, str2) << endl;
cin.getline(str1, 100);
}

return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s