通過刪除重複的子字符串來組合兩個字符串

Question

我有兩個字符串，我想合併，刪除重複的子字符串。請注意，每兩個連續的數字構成一個子串。考慮串str1和str2的：

str1 = "#100#123#100#678" 
str2 = "#100#678#100#56" 

我想產生組合的字符串：

comboStr = "#100#123#100#678#100#56" (i.e. I removed the duplicate #100#678) 

什麼是最簡單的方法是什麼？有沒有一種方法可以使用正則表達式來實現這一點？

Answer 1

我不認爲正則表達式是解決此問題的好方法。正則表達式在查找#123標記時可能會很有用，但問題需要以某種方式回溯到自己的字符串，而不要求使用正則表達式的後向引用。

我也不認爲有一個簡單的方法（如三行代碼）來解決這個問題。

我假定這些字符串總是遵循(#\d+)*的模式，並且在連接兩個字符串時在接縫處創建的對不是特殊的，也就是說，最終的對可能被認爲是重複的。這意味着我們可以從連接對移除中分離連接。

將您的字符串轉換爲整數列表，對這些列表進行操作，然後再將它們加入。這是一些工作，但它使實際的代碼更容易地去除重複項 - 它已經足夠複雜了 - 並且在需要經常操作類似字符串時也可能派上用場。

#include <stdlib.h> 
#include <stdio.h> 

/* 
*  Convert a string to a list of at most max integers. The 
*  return value is the number of integers in the list (which 
*  max be greater than max!) or -1 if the string is invalid. 
*/ 
int ilist_split(int *ilist, int max, const char *str) 
{ 
    const char *p = str; 
    int n = 0; 

    while (*p) { 
     int x; 
     int pos; 

     if (sscanf(p, "#%d %n", &x, &pos) < 1) return -1; 
     if (n < max) ilist[n] = x; 
     n++; 
     p += pos; 
    } 

    return n; 
} 

/* 
*  Convert a list of integers back to a string. The string 
*  is at most nbuf - 1 characters long and is assured to be 
*  zero-terminated if nbuf isn't 0. It is legal to pass NULL 
*  as char buffer if nbuf is 0. Returns the number of characters 
*  that would have been written ha dthe buffer been long enough, 
*  snprintf-style. 
*/ 
int ilist_join(const int *ilist, int n, char *buf, int nbuf) 
{ 
    int len = 0; 
    int i; 

    for (i = 0; i < n; i++) { 
     len += snprintf(buf + len, 
      nbuf > len ? nbuf - len : 0, "#%d", ilist[i]); 
    } 

    return len; 
} 

/* 
*  Auxliary function to find a pair in an inteher list. 
*/ 
int ilist_find_pair(int *ilist, int n, int a1, int a2) 
{ 
    int i; 

    for (i = 1; i < n; i++) { 
     if (ilist[i - 1] == a1 && ilist[i] == a2) return i - 1; 
    } 

    return -1; 
} 

/* 
*  Remove duplicate pairs from an integer list. The first 
*  pair is kept, subsequent pairs are deleted. Returns the 
*  new length of the array. 
*/ 
int ilist_remove_dup_pairs(int *ilist, int n) 
{ 
    int i, j; 

    j = 1; 
    for (i = 1; i < n; i++) { 
     int a1 = ilist[i - 1]; 
     int a2 = ilist[i]; 

     if (ilist_find_pair(ilist, i - 1, a1, a2) < 0) { 
      ilist[j++] = ilist[i]; 
     } else { 
      i++; 
     } 
    } 

    return j; 
} 



#define MAX 40 

int main() 
{ 
    const char *str1 = "#100#123#100#678"; 
    const char *str2 = "#100#678#100#56"; 
    char res[80]; 

    int ilist[MAX]; 
    int nlist; 

    /* convert str1 */ 
    nlist = ilist_split(ilist, MAX, str1); 
    if (nlist > MAX) nlist = MAX; 

    /* convert and concatenate str2 */ 
    nlist += ilist_split(ilist + nlist, MAX - nlist, str2); 
    if (nlist > MAX) nlist = MAX; 

    /* remove duplicate pairs */ 
    nlist = ilist_remove_dup_pairs(ilist, nlist); 

    /* convert back to string */ 
    ilist_join(ilist, nlist, res, sizeof(res)); 
    printf("%s\n", res); 

    return 0; 
}