Re: string function

[Herry Budiutama]

On Mon, 22 Feb 1999, Anubhav Hanjura wrote:

> can somebody give an efficient algorithm for this string manipulation function.
> Concat two strings s1,s2 in which some last char's of s1 are same as the first few 
>char's of s2 and we don't know how many. Write efficient code to concatanate these 2 
>strings so that the redundant char's appear just once. eg.
> s1="   india pakis";
> s2="kisme not";

This sounds like homework. :)  Here's O(n)...

#include <iostream.h>
#include <string.h>

int findcommon(const char* p1, const char* p2)
{
  if (!p1 || !p2) throw 0;
  register int i = 0, j = 0;
  int s;

  while (1)
    {
      while (p1[i] != p2[0] && i < strlen(p1))
        ++i;
      if (i == strlen(p1))
        return i;
      s = i;   
      while (i < strlen(p1))
        {
          if (p1[i] != p2[j])
            {
              j = 0;
              continue;
            }   
          ++i; ++j;   
        }
      return s;
    }
}

int main()
{

  const char* p1 = " india pakis";
  const char* p2 = "kisme not";

  char p3[1024];

  int z = findcommon(p1, p2);  
  strncpy(p3, p1, z);
  memcpy( &p3[z], p2, strlen(p2) );
  cout << p3 << endl;
  return 0;
}

- Herry