The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.
#include <iostream>
using namespace std;
bool is_substr(char *str, char *sub)
{
char *p1 = str;
char *p2 = sub;
int len1 = strlen(str);
int len2 = strlen(sub);
if(len2 > len1){
return false;
}
p1 = str;
while(len1 >= len2){
p2 = sub;
char *p3 = p1;
while(*p2 != '\0' && *p3 == *p2){
p3 ++;
p2 ++;
}
if(*p2 == '\0'){
return true;
}
p1 ++;
len1 --;
}
return false;
}
int longest_common_substr(char *str1, char *str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
int slen = len2;
int len3;
char *t;
// make str1 the longer string
if(len2 > len1){
t = str1;
str1 = str2;
str2 = t;
len3 = len1;
len1 = len2;
len2 = len3;
}
slen = len2;
while(slen > 0){
t = str2;
while(t + slen <= str2 + len2){
char tstr[100];
memcpy(tstr, t, slen);
tstr[slen] = '\0';
if(is_substr(str1, tstr)){
cout << tstr << endl;
return slen;
}
t++;
}
slen --;
}
return 0;
}
int main(int argc, char* argv[])
{
char *str1 = "notnecessary to go to";
char *str2 = "kind of you not a";
cout << longest_common_substr(str1, str2) << endl;
return 0;
}
Output
not
3