问题描述:
引用: Fun With Strings
根据问题描述，一种简单的方法如下:为所有可能的子字符串(对于给定的字符串)找到 LCP 的长度之和:
#include <cstring>
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
using std::string;
int lcp(string str1, string str2)
{
string result;
int n1 = str1.length(), n2 = str2.length();
// Compare str1 and str2
for (int i=0, j=0; i<=n1-1 && j<=n2-1; i++,j++)
{
if (str1[i] != str2[j])
break;
result.push_back(str1[i]);
}
return (result.length());
}
int main()
{
string s;
cin>>s;
int sum = 0;
for(int i = 0; i < s.length(); i++)
for(int j = i; j < s.length(); j++)
for(int k = 0; k < s.length(); k++)
for(int l = k; l < s.length(); l++)
sum += lcp(s.substr(i,j - i + 1),s.substr(k,l - k + 1));
cout<<sum<<endl;
return 0;
}
根据对LCP的进一步阅读和研究，我发现了这个document，它指定了一种使用称为的高级数据结构有效地查找LCP的方法Tries 。我实现了一个Trie和一个压缩的Trie(后缀树)，如下所示:
#include <iostream>
#include <cstring>
using std::cout;
using std::cin;
using std::endl;
using std::string;
const int ALPHA_SIZE = 26;
struct TrieNode
{
struct TrieNode *children[ALPHA_SIZE];
string label;
bool isEndOfWord;
};
typedef struct TrieNode Trie;
Trie *getNode(void)
{
Trie *parent = new Trie;
parent->isEndOfWord = false;
parent->label = "";
for(int i = 0; i <ALPHA_SIZE; i++)
parent->children[i] = NULL;
return parent;
}
void insert(Trie *root, string key)
{
Trie *temp = root;
for(int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if(!temp->children[index])
{
temp->children[index] = getNode();
temp->children[index]->label = key[i];
}
temp = temp->children[index];
temp->isEndOfWord = false;
}
temp->isEndOfWord = true;
}
int countChildren(Trie *node, int *index)
{
int count = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(node->children[i] != NULL)
{
count++;
*index = i;
}
}
return count;
}
void display(Trie *root)
{
Trie *temp = root;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i] != NULL)
{
cout<<temp->label<<"->"<<temp->children[i]->label<<endl;
if(!temp->isEndOfWord)
display(temp->children[i]);
}
}
}
void compress(Trie *root)
{
Trie *temp = root;
int index = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i])
{
Trie *child = temp->children[i];
if(!child->isEndOfWord)
{
if(countChildren(child,&index) >= 2)
{
compress(child);
}
else if(countChildren(child,&index) == 1)
{
while(countChildren(child,&index) < 2 and countChildren(child,&index) > 0)
{
Trie *sub_child = child->children[index];
child->label = child->label + sub_child->label;
child->isEndOfWord = sub_child->isEndOfWord;
memcpy(child->children,sub_child->children,sizeof(sub_child->children));
delete(sub_child);
}
compress(child);
}
}
}
}
}
bool search(Trie *root, string key)
{
Trie *temp = root;
for(int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if(!temp->children[index])
return false;
temp = temp->children[index];
}
return (temp != NULL && temp->isEndOfWord);
}
int main()
{
string input;
cin>>input;
Trie *root = getNode();
for(int i = 0; i < input.length(); i++)
for(int j = i; j < input.length(); j++)
{
cout<<"Substring : "<<input.substr(i,j - i + 1)<<endl;
insert(root, input.substr(i,j - i + 1));
}
cout<<"DISPLAY"<<endl;
display(root);
compress(root);
cout<<"AFTER COMPRESSION"<<endl;
display(root);
return 0;
}
我的问题是如何继续查找LCP的长度。我可以通过在分支节点上获取标签字段来获取LCP，但是如何计算所有可能的子字符串的LCP长度？
我想到的一种方法是，如何使用分支节点，包含LCP的标签字段以及分支节点的子节点来找到所有LCP长度的总和(最低公共(public)祖先吗？)。但是我仍然很困惑。我该如何进一步进行？
注意:我解决此问题的方法也可能是错误的，因此也请针对该问题建议其他方法(考虑时间和空间的复杂性)。
链接到 Unresolved 类似问题:
代码和理论引用:
Update1:
基于@Adarsh Anurag的回答，我提出了以下实现
借助trie数据结构，
#include <iostream>
#include <cstring>
#include <stack>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::stack;
const int ALPHA_SIZE = 26;
int sum = 0;
stack <int> lcp;
struct TrieNode
{
struct TrieNode *children[ALPHA_SIZE];
string label;
int count;
};
typedef struct TrieNode Trie;
Trie *getNode(void)
{
Trie *parent = new Trie;
parent->count = 0;
parent->label = "";
for(int i = 0; i <ALPHA_SIZE; i++)
parent->children[i] = NULL;
return parent;
}
void insert(Trie *root, string key)
{
Trie *temp = root;
for(int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if(!temp->children[index])
{
temp->children[index] = getNode();
temp->children[index]->label = key[i];
}
temp = temp->children[index];
}
temp->count++;
}
int countChildren(Trie *node, int *index)
{
int count = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(node->children[i] != NULL)
{
count++;
*index = i;
}
}
return count;
}
void display(Trie *root)
{
Trie *temp = root;
int index = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i] != NULL)
{
cout<<temp->label<<"->"<<temp->children[i]->label<<endl;
cout<<"CountOfChildren:"<<countChildren(temp,&index)<<endl;
cout<<"Counter:"<<temp->children[i]->count<<endl;
display(temp->children[i]);
}
}
}
void lcp_sum(Trie *root,int counter,string lcp_label)
{
Trie *temp = root;
int index = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i])
{
Trie *child = temp->children[i];
if(lcp.empty())
{
lcp_label = child->label;
counter = 0;
lcp.push(child->count*lcp_label.length());
sum += lcp.top();
counter += 1;
}
else
{
lcp_label = lcp_label + child->label;
stack <int> temp = lcp;
while(!temp.empty())
{
sum = sum + 2 * temp.top() * child->count;
temp.pop();
}
lcp.push(child->count*lcp_label.length());
sum += lcp.top();
counter += 1;
}
if(countChildren(child,&index) > 1)
{
lcp_sum(child,0,lcp_label);
}
else if (countChildren(child,&index) == 1)
lcp_sum(child,counter,lcp_label);
else
{
while(counter-- && !lcp.empty())
lcp.pop();
}
}
}
}
int main()
{
string input;
cin>>input;
Trie *root = getNode();
for(int i = 0; i < input.length(); i++)
for(int j = i; j < input.length(); j++)
{
cout<<"Substring : "<<input.substr(i,j - i + 1)<<endl;
insert(root, input.substr(i,j - i + 1));
display(root);
}
cout<<"DISPLAY"<<endl;
display(root);
cout<<"COUNT"<<endl;
lcp_sum(root,0,"");
cout<<sum<<endl;
return 0;
}
从Trie结构中，我删除了
isEndOfWord变量，而是将其替换为counter。此变量跟踪重复的子字符串，这应该有助于计算具有重复字符的字符串的LCP。但是，以上实现仅适用于具有不同字符的字符串。我尝试实现@Adarsh建议的方法来处理重复字符，但不满足任何测试用例。Update2:
根据来自@Adarsh的进一步更新的答案以及使用不同测试用例的“尝试和错误”，我似乎在重复字符方面有所进步，但是仍然无法按预期工作。这是带有注释的实现，
// LCP : Longest Common Prefix
// DFS : Depth First Search
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
using std::cout;
using std::cin;
using std::endl;
using std::string;
using std::stack;
using std::queue;
const int ALPHA_SIZE = 26;
int sum = 0; // Global variable for LCP sum
stack <int> lcp; //Keeps track of current LCP
// Trie Data Structure Implementation (See References Section)
struct TrieNode
{
struct TrieNode *children[ALPHA_SIZE]; // Search space can be further reduced by keeping track of required indicies
string label;
int count; // Keeps track of repeat substrings
};
typedef struct TrieNode Trie;
Trie *getNode(void)
{
Trie *parent = new Trie;
parent->count = 0;
parent->label = ""; // Root Label at level 0 is an empty string
for(int i = 0; i <ALPHA_SIZE; i++)
parent->children[i] = NULL;
return parent;
}
void insert(Trie *root, string key)
{
Trie *temp = root;
for(int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a'; // Lowercase alphabets only
if(!temp->children[index])
{
temp->children[index] = getNode();
temp->children[index]->label = key[i]; // Label represents the character being inserted into the node
}
temp = temp->children[index];
}
temp->count++;
}
// Returns the count of child nodes for a given node
int countChildren(Trie *node, int *index)
{
int count = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(node->children[i] != NULL)
{
count++;
*index = i; //Not required for this problem, used in compressed trie implementation
}
}
return count;
}
// Displays the Trie in DFS manner
void display(Trie *root)
{
Trie *temp = root;
int index = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i] != NULL)
{
cout<<temp->label<<"->"<<temp->children[i]->label<<endl; // Display in this format : Root->Child
cout<<"CountOfChildren:"<<countChildren(temp,&index)<<endl; // Count of Child nodes for Root
cout<<"Counter:"<<temp->children[i]->count<<endl; // Count of repeat substrings for a given node
display(temp->children[i]);
}
}
}
/* COMPRESSED TRIE IMPLEMENTATION
void compress(Trie *root)
{
Trie *temp = root;
int index = 0;
for(int i = 0; i < ALPHA_SIZE; i++)
{
if(temp->children[i])
{
Trie *child = temp->children[i];
//if(!child->isEndOfWord)
{
if(countChildren(child,&index) >= 2)
{
compress(child);
}
else if(countChildren(child,&index) == 1)
{
while(countChildren(child,&index) < 2 and countChildren(child,&index) > 0)
{
Trie *sub_child = child->children[index];
child->label = child->label + sub_child->label;
//child->isEndOfWord = sub_child->isEndOfWord;
memcpy(child->children,sub_child->children,sizeof(sub_child->children));
delete(sub_child);
}
compress(child);
}
}
}
}
}
*/
// Calculate LCP Sum recursively
void lcp_sum(Trie *root,int *counter,string lcp_label,queue <int> *s_count)
{
Trie *temp = root;
int index = 0;
// Traverse through this root's children array, to find child nodes
for(int i = 0; i < ALPHA_SIZE; i++)
{
// If child nodes found, then ...
if(temp->children[i] != NULL)
{
Trie *child = temp->children[i];
// Check if LCP stack is empty
if(lcp.empty())
{
lcp_label = child->label; // Set LCP label as Child's label
*counter = 0; // To make sure counter is not -1 during recursion
/*
* To include LCP of repeat substrings, multiply the count variable with current LCP Label's length
* Push this to a stack called lcp
*/
lcp.push(child->count*lcp_label.length());
// Add LCP for (a,a)
sum += lcp.top() * child->count; // Formula to calculate sum for repeat substrings : (child->count) ^ 2 * LCP Label's Length
*counter += 1; // Increment counter, this is used further to pop elements from the stack lcp, when a branching node is encountered
}
else
{
lcp_label = lcp_label + child->label; // If not empty, then add Child's label to LCP label
stack <int> temp = lcp; // Temporary Stack
/*
To calculate LCP for different combinations of substrings,
2 -> accounts for (a,b) and (b,a)
temp->top() -> For previous substrings and their combinations with the current substring
child->count() -> For any repeat substrings for current node/substring
*/
while(!temp.empty())
{
sum = sum + 2 * temp.top() * child->count;
temp.pop();
}
// Similar to above explanation for if block
lcp.push(child->count*lcp_label.length());
sum += lcp.top() * child->count;
*counter += 1;
}
// If a branching node is encountered
if(countChildren(child,&index) > 1)
{
int lc = 0; // dummy variable
queue <int> ss_count; // queue to keep track of substrings (counter) from the child node of the branching node
lcp_sum(child,&lc,lcp_label,&ss_count); // Recursively calculate LCP for child node
// This part is experimental, does not work for all testcases
// Used to calculate the LCP count for substrings between child nodes of the branching node
if(countChildren(child,&index) == 2)
{
int counter_queue = ss_count.front();
ss_count.pop();
while(counter_queue--)
{
sum = sum + 2 * ss_count.front() * lcp_label.length();
ss_count.pop();
}
}
else
{
// Unclear, what happens if children is > 3
// Should one take combination of each child node with one another ?
while(!ss_count.empty())
{
sum = sum + 2 * ss_count.front() * lcp_label.length();
ss_count.pop();
}
}
lcp_label = temp->label; // Set LCP label back to Root's Label
// Empty the stack till counter is 0, so as to restore it's state when it first entered the child node from the branching node
while(*counter)
{
lcp.pop();
*counter -=1;
}
continue; // Continue to next child of the branching node
}
else if (countChildren(child,&index) == 1)
{
// If count of children is 1, then recursively calculate LCP for further child node
lcp_sum(child,counter,lcp_label,s_count);
}
else
{
// If count of child nodes is 0, then push the counter to the queue for that node
s_count->push(*counter);
// Empty the stack till counter is 0, so as to restore it's state when it first entered the child node from the branching node
while(*counter)
{
lcp.pop();
*counter -=1;
}
lcp_label = temp->label; // Set LCP label back to Root's Label
}
}
}
}
/* SEARCHING A TRIE
bool search(Trie *root, string key)
{
Trie *temp = root;
for(int i = 0; i < key.length(); i++)
{
int index = key[i] - 'a';
if(!temp->children[index])
return false;
temp = temp->children[index];
}
return (temp != NULL );//&& temp->isEndOfWord);
}
*/
int main()
{
int t;
cin>>t; // Number of testcases
while(t--)
{
string input;
int len;
cin>>len>>input; // Get input length and input string
Trie *root = getNode();
for(int i = 0; i < len; i++)
for(int j = i; j < len; j++)
insert(root, input.substr(i,j - i + 1)); // Insert all possible substrings into Trie for the given input
/*
cout<<"DISPLAY"<<endl;
display(root);
*/
//LCP COUNT
int counter = 0; //dummy variable
queue <int> q; //dummy variable
lcp_sum(root,&counter,"",&q);
cout<<sum<<endl;
sum = 0;
/*
compress(root);
cout<<"AFTER COMPRESSION"<<endl;
display(root);
*/
}
return 0;
}
另外，这是一些示例测试用例(预期的输出)，
1. Input : 2 2 ab 3 zzz
Output : 6 46
2. Input : 3 1 a 5 afhce 8 ahsfeaa
Output : 1 105 592
3. Input : 2 15 aabbcceeddeeffa 3 bab
Output : 7100 26
对于测试用例2和3(部分输出)，以上实现失败。请提出解决此问题的方法。解决此问题的任何其他方法也可以。
最佳答案
您的直觉正在朝着正确的方向发展。
基本上，每当看到子字符串的LCP问题时，都应该考虑诸如suffix trees，suffix arrays和suffix automata之类的后缀数据结构。后缀树可以说是功能最强大，最容易处理的树，它们可以很好地解决此问题。
后缀树是一个trie，包含字符串的所有满足条件，每个非分支边缘链都压缩为单个长边缘。具有所有条件的普通trie的问题在于它具有O(N ^ 2)个节点，因此需要O(N ^ 2)个内存。假定您可以使用琐碎的动态编程预先计算O(N ^ 2)时间和空间中所有对的LCP，那么没有压缩的后缀树就不好了。
压缩的特里占用O(N)内存，但是如果您使用O(N ^ 2)算法构建它，则仍然无效(就像您在代码中所做的那样)。您应该使用Ukkonen's algorithm以O(N)时间的压缩形式直接构造后缀树。学习和实现此算法并非易事，也许您会发现web visualization很有帮助。最后一点，为简单起见，我将在字符串的末尾添加一个定点字符(例如dollar $)，以确保所有叶子都是后缀树中的显式节点。
注意:
这是主要思想。考虑所有成对的子字符串，并将它们分为具有相同LCA顶点的组。换句话说，让我们计算A [v]:= LCA顶点正好为v的子字符串对的数量。如果为每个顶点v计算此数量，那么剩下的要解决的问题是:将每个数字乘以节点的深度并获得总和。同样，数组A [*]仅占用O(N)空间，这意味着我们还没有失去在线性时间内解决整个问题的机会。
回想一下，每个子字符串都是根节点路径。考虑两个节点(代表两个任意子字符串)和一个顶点v。让我们将在顶点v处具 Root过的子树称为“v子树”。然后:
让我们介绍另一个数量B [v]:= LCA顶点在v-subtree内的子串对的数量。上面的语句显示了一种计算B [v]的有效方法:它只是v子树中节点数的平方，因为其中的每对节点都符合标准。但是，此处应考虑多重性，因此每个节点必须计入与其对应的子字符串一样多的次数。
公式如下: B[v] = Q[v]^2
Q[v] = sum_s( Q[s] + M[s] * len(vs) ) for s in sons(v)
M[v] = sum_s( M[s] ) for s in sons(v)
M [v]是顶点的多重性(即v子树中存在多少个叶子)，而Q [v]是v子树中考虑了多重性的节点数。当然，您可以自己推断出叶子的基本情况。使用这些公式，您可以在O(N)时间内遍历树时计算M [*]，Q [*]，B [*]。
仅需使用B [*]数组来计算A [*]数组。可以通过简单排除公式在O(N)中完成:A[v] = B[v] - sum_s( B[s] ) for s in sons(v)
如果实现所有这些，您将能够在完美的O(N)时间和空间上解决整个问题。或更好地说:O(N C)时空，其中C是字母的大小。