我有这个程序,它应该找到多个字符串的最长公共子字符串。它确实如此,但如果字符串很长(即> 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;
}
注意:我没有编写可以用后缀树解决这个问题的代码是有原因的(它们很大)。