StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Tuesday, February 26, 2013

Longest common sub-string of two given strings using suffix array

 February 26, 2013     Programming problems in CPP     No comments   

Write a program to find the longest common sub-string of two given strings.

For example, given two strings, "philologist" and "lollipop", "lol" is the LCS.
Here we use suffix arrays.

The approach:-

  1. Create a char pointer array pointing each of the character in the first string. Similarly create another array for second string

  2. suffixarray
  3. Re-order the pointers in the arrays, using qsort, so that the string pointed to by them are in sorted order.

  4. sortedsuffixarray
  5. Finally use "merge two sorted linked list" kind of technique to compare the strings and look for the match (full or partially) and keep track of the longest one during iteration.

The solution:-

#include <stdio.h> /* printf */
#include <stdlib.h> /* qsort */
#include <string.h>

// Used for quicksort
int compare(const void *a, const void *b)
{
const char* a1 = *(const char**)a;
const char* b1 = *(const char**)b;
return strcmp(a1,b1);
}

//create a pointer list to each of the characters in the input.
char** formSuffixList(char* input)
{
char ** sub_str = (char **)malloc(strlen(input) * sizeof(char*));
char *tmp = input;
int i = 0;
while (*tmp != '\0' ) {
sub_str[i] = tmp;
tmp++; i++;
}
return sub_str;
}

//returns position where the change is. And the sign tells which is higher value.
int matchstr(const char *a, const char *b)
{
int i=0;
while(*a == *b) {
if ( *a == '\0' || *b == '\0' )
break;
i++;a++;b++;
}
i++;
if (*a == '\0')
return i;
if (*b == '\0')
return -i;

if (*a > *b)
return i;
else
return -i;
}

int main()
{
int c1, c2;

char* str1 = "madmandogcat";
char* str2 = "xyzdmanzyandogcio";

char** _array1 = formSuffixList(str1);
char** _array2 = formSuffixList(str2);

c1 = strlen(str1);
c2 = strlen(str2);
qsort(_array1,c1, sizeof(char*),compare);
qsort(_array2,c2, sizeof(char*),compare);

int best = 0;
char *lcs;
c1--;c2--;
while ( (c1>=0) && (c2>=0)) {
int n = matchstr(_array1 [c1],_array2 [c2]);
if ( abs(n)-1 > best) {
best = abs(n)-1;
lcs = _array1 [c1];
}
if (n > 0)
c1--;
else
c2--;
}
char* res = (char*)malloc(best+1);
memcpy(res,lcs,best);
res[best] = '\0';
printf ("LCS len: %d and string: %s\n",best, res);
delete res;
delete _array1;
delete _array2;
}


Output:-
LCS len: 6 and string: andogc
Email ThisBlogThis!Share to XShare to Facebook
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Python FastAPI file upload and download
    In this article, we will look at an example of how to implement a file upload and download API in a Python FastAPI microservice. Example bel...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Accessing the Kubernetes API
    In this article, we will explore the steps required to access the Kubernetes API and overcome common challenges. All operations and communic...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Scheduling jobs in Python
    When developing applications and microservices we run into scenarios where there is a need to run scheduled tasks. Examples include performi...
  • Using Tekton to deploy KNative services
    Tekton is a popular open-source framework for building continuous delivery pipelines. Tekton provides a declarative way to define pipelines ...

Copyright © StackStalk