Algorithm of finding the duplicated sub-strings in two strings

Article
09/28/2007

One tough issue, especially require the better performance and memory usage.

However, I done it :)

1. It builds a table strlen(s1)*strlen(s2)
2. Compare the s1 and s2 and fill the equaled bit in the table
3. Find out the longest connected lines in that table
4. Re-build the string with the line's offset

Not sure if it is the best algorithm to do that :)

However it only spend 47ms to compare and find out the duplicate string ("pro") of "programming" and "professional" in 10000 times.

"abbazyabcyzabcegz" and ""xabcyzabcdegabbazyabh" for 10,000 times
Milliseconds: 109

Cool?

//////

StrNode* GetDupStr(__notnull LPCWSTR lpszP1, __notnull LPCWSTR lpszP2)
{
   // 0. valid parameters, if SAL does not work
   if (lpszP1==NULL || lpszP2==NULL || wcslen(lpszP1)==0 || wcslen(lpszP2)==0)
       return NULL;
   //
   // 1. build the table
   //
   // calculate the size
   int nLen1 = (int)wcslen(lpszP1);
   int nLen2 = (int)wcslen(lpszP2);
   int nMapLen = sizeof(bool)*nLen1*nLen2;
   // allocate the memory @allocate abMap
   bool* abMap;
   abMap = (bool*)malloc(nMapLen);
   //ZeroMemory
   memset(abMap, 0x0, nMapLen);

   //
   // 2. compare and fill the table
   //
   for(int i=0; i<nLen1; i++)
   //rows
   {
       WCHAR cRow = lpszP1[i];
       //check if there is duplicated char in previous chars, if so, memcpy directly
       for(int k=0; k<i; k++)
       {
           if (lpszP1[k]==cRow)
           {
               memcpy(&abMap[i*nLen2], &abMap[k*nLen2], nLen2);
               DEBUG("Dup: %c\n", cRow);
           }
       }
       //loop cols
       for(int j=0; j<nLen2; j++)
       //cols
       {
           //check equality
           if (cRow==lpszP2[j])
           {
               //MarkEqual(abMap, CalPos(nLen2, i, j));
               MarkBit(abMap, CalcBitPos(nLen2, i, j));
           }
       }
   }

   //
   // 3. print out the table
   //
#ifdef _DUPSTR_DEBUG_
   PrintTable(abMap, lpszP1, lpszP2);
   DEBUG("\n", NULL);
#endif

   //
   // 4. search table, find out the connected points
   //
   // get minimun strlen of two strings
   int nMinLen = nLen1 < nLen2 ? nLen1 : nLen2;
   // build maxNode var @allocate pMaxNode
   BNode *pMaxNode = NULL;
   //
   // loop the cols and rows from longest to shortest, and compare the maxlength with current nLen
   // jump out if maxLen > nLen
   //
   //loop for cols
   for(int i=0; i<nLen2; i++)
   {
       //current len
       int nLen = nMinLen < nLen2-i ? nMinLen : nLen2-i;
       if ( pMaxNode==NULL || pMaxNode->len<nLen)
       {
           //get pNodes
           BNode *pNode = CheckPoints(&abMap[CalcBitPos(nLen2, 0, i)], nLen, nLen2+1);
           //rebuild
           RebuildMaxNodes(&pMaxNode, &pNode);
       }
   }
   //then loop for rows
   for(int i=1; i<nLen1; i++)
   {
       int nLen = nMinLen < nLen1-i ? nMinLen : nLen1-i;
       if ( pMaxNode==NULL || pMaxNode->len<nLen)
       {
           BNode *pNode = CheckPoints(&abMap[CalcBitPos(nLen2, i, 0)], nLen, nLen2+1);
           /* @refactor RebuildMaxNodes
           if (pNode!=NULL)
           {
               if (pMaxNode==NULL)
               {
                   DEBUG("leave null\n", NULL);
                   pMaxNode = pNode;
               }
               else if (pMaxNode->len < pNode->len)
               {
                   DEBUG("got new length: %d\n", pNode->len);
                   //free previous pMaxNode
                   ReleaseNode(pMaxNode);
                   pMaxNode = pNode;
               }
               else if (pMaxNode->len == pNode->len)
               {
                   DEBUG("get duplicated\n", NULL);
                   pMaxNode->next = pNode;
               }
               else
               {
                   ReleaseNode(pNode);
               }
           }
           */
           RebuildMaxNodes(&pMaxNode, &pNode);
       }
   }

   //
   // 5. print out pMaxNodes
   //
   StrNode* pstrNode = NULL;
   //
   BNode* pn = pMaxNode;
   //foreach pMaxNode
   while(pn!=NULL)
   {
       //calculate the string offset
       int nStrOffset = (int)((pn->pbStart - abMap) % nLen2);
       //allocate new string @allocate lpszOutput
       LPWSTR lpszOutput = new WCHAR[pn->len+1];
       memset(lpszOutput, 0x0, (pn->len+1)*sizeof(WCHAR));
       memcpy(lpszOutput, lpszP2+nStrOffset, pn->len * sizeof(WCHAR));

       DEBUG("%x => ", pn->pbStart);
       DEBUG("%d => ", pn->len);
       DEBUG("%s\n", lpszOutput);
       //DEBUG("%x => %d => %s\n", pn->pbStart, pn->len, lpszOutput);

       //attach string to return structure
       if (pstrNode==NULL)
       {
           //build the node
           pstrNode = BuildStrNode(lpszP2+nStrOffset, pn->len, lpszOutput);
           HEAPLEAK(pstrNode->magic, 0xCACF0169);
       }
       else
       {
           //build the node
           /* @refactor BuildStrNode
           StrNode* psn = new StrNode;
           memset(psn, 0x0, sizeof(StrNode));
           psn->lpSrc = lpszP2+nStrOffset;
           psn->len = pn->len;
           psn->str = lpszOutput;
           psn->next = NULL;
           pstrNode->next = psn;
           */
           StrNode* psn = pstrNode;
           while(psn->next!=NULL)
           {
               psn = psn->next;
           }
           psn->next = BuildStrNode(lpszP2+nStrOffset, pn->len, lpszOutput);
           HEAPLEAK(psn->next->magic, 0xCACF0189);
       }

       pn = pn->next;
   }
   //@release pMaxNode
   ReleaseBNode(pMaxNode);
   //@release abMap
   delete abMap;

return pstrNode;
}

Attached full code files.

MaxDuplicatedString.7z

Share via

Algorithm of finding the duplicated sub-strings in two strings

Additional resources