题目解析：求回声字符串的个数，也就是求头半段等于后半段的字符串的个数。
解法一：遍历长度为l的每一子字符串，时间复杂度为O(n^2) , 判断子字符串的的前半段是否等于后半段，总的时间复杂度为O(N^3).会超时；
class Solution {
public:
int distinctEchoSubstrings(string text)
{
int len = text.size() ;
//vector<vector<int>> dp(len , vector<int>(len , 0)) ;
//int modl = 1e18 + 7 ;
unordered_set<string> res ;
for(int split = 1 ; split < len ; split++)
for(int l = 1 ; split - l >= 0 && split + l <= len ; l++)
if(text.compare(split - l , l , text , split , l) == 0) res.insert(text.substr(split , l)) ;
return res.size() ;
}
};
解法二：优化：使用kmp算法，求每一子字符串的kmp长度是否大于等于子字符串长度的一半，若等于一半就一定满足条件；但是还得进一步考虑如果大于一半的情况，如果(l/2%(l - kmpl) == 0)，则满足条件。时间复杂度近似为O(N^2logN) , 空间复杂度为O(N^2);可进一步将空间复杂度优化为O(N) ;
class Solution {
public:
int distinctEchoSubstrings(string text)
{
int len = text.size() ;
vector<vector<int>> dp(len , vector<int>(len , 0)) ;
unordered_set<string> res ;
for(int i = 0 ; i < len ; i++)
{
for(int j = i + 1 ; j < len ; j++)
{
int k = dp[i][j-1] ;
while(k != 0 && text[i+k] != text[j] ) k = dp[i][i + k - 1] ;
if(text[i+k] == text[j]) k++ ;
dp[i][j] = k ;
if((j - i + 1) % 2 == 0 && k * 2 >= j - i + 1 && (j - i + 1) / 2 % (j - i + 1 - k) == 0) res.insert(text.substr(i , j - i + 1)) ;
}
}
return res.size() ;
}
};
解法三：使用滚动hash的方法，计算字符串的hash值，那么就可以在O(1)时间比较两字符串是否相等 ， 但是因为l长度最多为2000，可能会存在hash冲突。但是因为比较的两个字符串长度一样，所以不必担心hash冲突。时间复杂度降为O(N^2）；
class Solution {
public:
int distinctEchoSubstrings(string text)
{
int len = text.size() ;
//vector<vector<int>> dp(len , vector<int>(len , 0)) ;
int modl = 1e9 + 7 ;
unordered_set<string> res ;
for(int split = 1 ; split < len ; split++)
{
long long hashl = 0 , hashr = 0 , base = 1 ;
for(int l = 1 ; split - l >= 0 && split + l <= len ; l++)
{
hashl = (hashl + base * (text[split - l] - ‘a‘)) % modl ;
hashr = (hashr * 26 + text[split + l - 1] - ‘a‘) % modl;
base = (base * 26) % modl;
if(hashl == hashr) res.insert(text.substr(split , l)) ;
}
}
return res.size() ;
}
};
解法四：为了避免回声字符串重复，将所有字符串插入到unordered_set<string>中，但是字符串插入到hashset中还需要hash一次，重复计算了字符串的hash值，所以可以直接插入字符串的hash值；
class Solution {
public:
int distinctEchoSubstrings(string text)
{
int len = text.size() ;
//vector<vector<int>> dp(len , vector<int>(len , 0)) ;
long long modl = 1e15 + 7 ;
unordered_set<int> res ;
for(int split = 1 ; split < len ; split++)
{
long long hashl = 0 , hashr = 0 , base = 1 ;
for(int l = 1 ; split - l >= 0 && split + l <= len ; l++)
{
hashl = (hashl + base * (text[split - l])) % modl ;
hashr = (hashr * 26 + text[split + l - 1]) % modl;
base = (base * 26) % modl;
//cout<<text.substr(split - l , l)<<" "<<hashl<<" "<<text.substr(split , l)<<" "<<hashr<<endl;
if(hashl == hashr) res.insert(hashl) ;
}
}
return res.size() ;
}
};
原文：https://www.cnblogs.com/mychen06/p/12590836.html