Given two String, s1 and s2.
to find the longest substring which is prefix of s1, as well as suffix of s2.
Complexity O(n)
#include <stdio.h>
#include <string.h>
main()
{
char str1[]="abcdeee";
char str2[]="sssssabc";
int i=0,j,k,l;
int n=strlen(str2);
if(strlen(str1)<strlen(str2)){
n=strlen(str1);
}
k=0;
l=0;
for(i=0;i<n;i++){
j=strlen(str2)-n+i;
if(str1[l++]!=str2[j]){
i=k;
k++;
l=0;
}
}
printf("%s",str2+strlen(str2)-n+k);
}
to find the longest substring which is prefix of s1, as well as suffix of s2.
Complexity O(n)
#include <stdio.h>
#include <string.h>
main()
{
char str1[]="abcdeee";
char str2[]="sssssabc";
int i=0,j,k,l;
int n=strlen(str2);
if(strlen(str1)<strlen(str2)){
n=strlen(str1);
}
k=0;
l=0;
for(i=0;i<n;i++){
j=strlen(str2)-n+i;
if(str1[l++]!=str2[j]){
i=k;
k++;
l=0;
}
}
printf("%s",str2+strlen(str2)-n+k);
}
No comments:
Post a Comment