c++ - 优化思路——最长公共(public)子串

Question

我有这个程序，它应该找到多个字符串的最长公共(public)子串。它确实如此，但如果字符串很长(即 >8000 个字符长)，它运行缓慢(1.5 秒)。有什么办法可以优化吗？

程序是这样的:

//#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>


using namespace std;

const unsigned short MAX_STRINGS = 10;
const unsigned int  MAX_SIZE=10000;
vector<string> strings;
unsigned int len;

string GetLongestCommonSubstring( string string1, string string2 );
inline void readNumberSubstrings();
inline const string getMaxSubstring();

void readNumberSubstrings()
{
    cin >> len;

    assert(len > 1 && len <=MAX_STRINGS);

    strings.resize(len);

    for(register unsigned int i=0; i<len;i++)
        strings[i]=string(MAX_SIZE,0);

    for(register unsigned int i=0; i<len; i++)
        cin>>strings[i];
}

 const string getMaxSubstring()
{
    string maxSubstring=strings[0];
    for(register unsigned int i=1; i < len; i++)
        maxSubstring=GetLongestCommonSubstring(maxSubstring, strings[i]);
    return maxSubstring;
}

string GetLongestCommonSubstring( string string1, string string2 ) 
{

    const int solution_size = string2.length()+ 1;

    int *x=new int[solution_size]();
    int *y= new int[solution_size]();

    int **previous = &x;
    int **current = &y;

    int max_length = 0;
    int result_index = 0;

    int j;
    int length;
    int M=string2.length() - 1;

    for(register int i = string1.length() - 1; i >= 0; i--)
    {
        for(register int j = M; j >= 0; j--) 
        {
            if(string1[i] != string2[j]) 
                (*current)[j] = 0;
            else 
            {
                length = 1 + (*previous)[j + 1];
                if (length > max_length)
                {
                    max_length = length;
                    result_index = i;
                }

                (*current)[j] = length;
            }
        }

        swap(previous, current);
    }
    string1[max_length+result_index]='\0';
    return &(string1[result_index]);
}

int main()
{
    readNumberSubstrings();
    cout << getMaxSubstring() << endl;
    return 0;
}

注意:我没有编写代码来解决这个后缀树问题(它们很大)是有原因的。

Answer 1

通常在优化方面，不同的方法可能是您唯一真正的选择，而不是尝试逐步改进当前的实现。这是我的想法:

• 创建可能出现在最长公共(public)子串中的有效字符列表。即，如果一个字符没有出现在所有字符串中，则它不可能是最长公共(public)子字符串的一部分。

• 将每个字符串分成多个只包含有效字符的字符串

• 对于每个这样的字符串，创建每个可能的子字符串并将其也添加到列表中

• 过滤(与字符一样)所有未显示在所有列表中的字符串。

这个的复杂性显然很大程度上取决于无效字符的数量。如果它为零，则此方法根本无济于事。

关于您的代码的一些评论:不要试图变得过于聪明。编译器会优化很多，你真的没有必要在你的代码中加入 register 。其次，您分配字符串然后覆盖它们(在 readNumberSubstrings 中)，这是完全没有必要的。第三，如果可以的话，通过 const 引用传递。第四，不要使用原始指针，尤其是如果您从不delete [] 您的new []d 对象。请改用 std::vector，它在异常情况下表现良好(您可能会遇到这种情况，因为您经常使用字符串!)。