简单？复杂？——连续出现次数最多的子串(1)

最新推荐文章于 2021-09-08 23:17:37 发布

rushman

最新推荐文章于 2021-09-08 23:17:37 发布

阅读量3.8k

点赞数 1

分类专栏：算法 C/C++ 文章标签： buffer 算法测试面试微软

本文链接：https://blog.csdn.net/rushman/article/details/2344720

版权

C/C++ 同时被 2 个专栏收录

7 篇文章

订阅专栏

算法

4 篇文章

订阅专栏

问题的提出：

前几天，网友提出了一个问题：找出一段文本中连续出现次数最多的子串。
据说，这是微软的面试题。

乍一看，这个问题有点无从下手。难不成要列出所有可能的子串一个一个搜索计数？

我们还是先寻找一些规律。

最基本的，长度为 n 的字符串 S 多次连续出现 S1 S2 S3……，
则每次出现的起始位置P(S1) P(S2) P(S3)……，两两之间的差是相等的：P(S1) - P(S2) = P(S2) - P(S3) ……。

好像有点废话，但这确实是个规律。
以此，我们就可以设计一个简单的算法。

一个简单的算法：

举个简单的例子，比如输入的文本为“sabsababsabab"。
对于长度为 N 的文本 T ，我们可以按照子串的不同长度 n（1<= n <=K，K<=N/2）多次遍历文本查找在 n 步长的情况下相同的子串：

初始化 MAX_REPEAT = 1 // 只要字符出现就有一次了
STEP = 1 TO N / MAX_REPEAT
STEP = 1：
       sabsababsabab
<-   sabsababsabab
       ------------
没有相同的子串

STEP = 2：
       sabsababsabab
<- sabsababsabab
       ----12---12
           R1   R2
R1 是连续两个字符相同，它的重复次数是 REPEAT = COUNT(R1) / STEP + 1 = 2，即连续出现 2 次，由于 REPEAT > MAX_REPEAT，则令 MAX_REPEAT = REPEAT（并清除原有的结果），并保留结果 R1。
R2 的情况相同。
得到两个长度为 2 的子串R1 R2，他们均连续出现 2 次

STEP = 3：
       sabsababsabab
<- sabsababsabab
       123---12--
       R3    R4
R3 是连续 3 个相同的字符，重复次数是 COUNT(R1) / STEP + 1 = 2。由于 REPEAT = MAX_REPEAT，保留该结果。
R4 是连续 2 个相同的字符，重复次数是 COUNT(R1) / STEP + 1 = 1。由于 REPEAT < MAX_REPEAT，该结果。

STEP = 4：
       sabsababsabab
<- ...ababsabab
       ---------
没有相同的子串。

STEP = 5：
       sabsababsabab
<- ...babsabab
       -1234567
        R5
找到长度为 7 的相同的子串 R5，重复次数为 REPEAT = COUNT(R1) / STEP + 1 = 2。 REPEAT = MAX_REPEAT，保留该结果。需要注意的是，连续相等的字符有 7 个，大于当前的步长 5，这意味着它有若干个长度为 5 的子串都是连续出现 2 次。

......

最终得到的结果是：
R1 : ab
R2 : ab
R3 : sab
R5 : absab
     bsaba
     sabab

程序：

 
    
   #pragma 
    warning ( disable : 4786 ) 
   

 
   #include  
   < 
   iostream 
   > 
   
#include  
   < 
   string 
   > 
   
#include  
   < 
   list 
   > 
   
#include  
   < 
   set 
   > 
   

 
   #define 
    BUFFSIZE 1024 
   

 
   using 
    std::cout;
 
   using 
    std::endl;
 
   using 
    std:: 
   string 
   ;
 
   using 
    std:: 
   set 
   ;
 
   using 
    std::list;

 
   struct 
    RESULTITEM 
   ... 
   {
    size_t pos;
    size_t step;
    size_t len;
    RESULTITEM():pos(0),step(0),len(0)...{}
    RESULTITEM(size_t p, size_t s, size_t l):pos(p),step(s),len(l)...{}
    RESULTITEM(const RESULTITEM& r):pos(r.pos),step(r.step),len(r.len)...{}
} 
   ;

typedef list 
   < 
   RESULTITEM 
   > 
    RESULTSET;

 
   void 
    RecordResult(RESULTSET 
   & 
    result, size_t pos, size_t len, size_t step) 
   ... 
   {
    RESULTITEM item;
    item.pos = pos;
    item.len = len;
    item.step = step;

    result.push_back(item);
} 
   

 
   int 
    ScanText(RESULTSET 
   & 
    result,  
   const 
     
   string 
   & 
    text) 
   ... 
   {
    size_t pos, step;
    size_t repeat, max_repeat;
    size_t count;
    size_t textlen;
    const char* ctext;

    // 判断时包括结束的'/0'字符以简化逻辑
    textlen = text.length() + 1;
    ctext = text.c_str();
    for(max_repeat = 1, step = 1; step * max_repeat < textlen; step++)...{
        for(count = 0, pos = 0; pos + step < textlen; pos++)...{
            // 计数
            if(ctext[pos] == ctext[pos + step])...{
                count++;
                continue;
            }

            // 连续出现的次数
            repeat = count / step + 1;

            // 无连续出现或连续出现的次数较少
            if(repeat == 1 || repeat < max_repeat)...{
                count = 0;
                continue;
            }

            // 发现连续出现次数更多的子串
            if(repeat > max_repeat)...{
                result.clear();
                max_repeat = repeat;
            }

            RecordResult(result, pos - count, count, step);

            count = 0;
        }
    }

    return max_repeat;
} 
   


 
   void 
    ListFullResult( 
   const 
    RESULTSET 
   & 
    result,  
   const 
     
   string 
   & 
    text) 
   ... 
   {
    RESULTSET::const_iterator iter;
    size_t i, mod;

    cout<<"Text :""<<text<<"""<<endl<<endl;
    cout<<"Result :"<<endl;
    cout<<"--------"<<endl;
    for(iter = result.begin(); iter != result.end(); iter++)...{
        for(i = 0, mod = (iter->len % iter->step); i <= mod; i++)...{
            cout<<iter->pos<<" "<<iter->len<<":"<<text.substr(iter->pos + i, iter->step)<<endl;
        }
    }
    cout<<"--------"<<endl;
    cout<<"Total :"<<result.size()<<endl;
} 
   

 
   void 
    ListResult( 
   const 
    RESULTSET 
   & 
    result,  
   const 
     
   string 
   & 
    text) 
   ... 
   {
    RESULTSET::const_iterator iter;
    set<string> strset;
    string str;
    size_t i, mod;

    cout<<"Text :""<<text<<"""<<endl<<endl;
    cout<<"Result :"<<endl;
    cout<<"--------"<<endl;
    for(iter = result.begin(); iter != result.end(); iter++)...{
        for(i = 0, mod = (iter->len % iter->step); i <= mod; i++)...{
            str = text.substr(iter->pos + i, iter->step);
            if(!strset.count(str))...{
                strset.insert(str);
                cout<<str<<endl;
            }
        }
    }
    cout<<"--------"<<endl;
    cout<<"Total :"<<strset.size()<<endl;
} 
   

 
   void 
    GetText( 
   string 
   & 
    text) 
   ... 
   {
    char buffer[BUFFSIZE];
    while(!feof(stdin))...{
        if(fgets(buffer, sizeof(buffer), stdin))
            text += buffer;
    }
} 
   

 
   void 
    main( 
   void 
   ) 
   ... 
   {
    RESULTSET result;
    string text;
    int max_repeat;

    GetText(text);

    max_repeat = ScanText(result, text.c_str());
//    ListResult(result, text);
    ListFullResult(result, text);

    cout<<endl<<"Bye!"<<endl;
} 
   
 
  

测试 1 ：
Text :"sabsababsabab
"

Result :
--------
4 2:ab
9 2:ab
0 3:sab
1 7:absab
1 7:bsaba
1 7:sabab
--------
Total :4

Bye!

测试 2 ：
Text :"sabsabsababsababsabababc
sabsabsababsababsabababc
sabsabsababsababsabababc
"

Result :
--------
17 4:ab
42 4:ab
67 4:ab
0 6:sab
25 6:sab
50 6:sab
4 12:absab
4 12:bsaba
4 12:sabab
29 12:absab
29 12:bsaba
29 12:sabab
54 12:absab
54 12:bsaba
54 12:sabab
0 50:sabsabsababsababsabababc

--------
Total :10

Bye!