9

问题描述： 参考：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 的进一步阅读和研究，我发现了这个文档，它指定了一种使用称为Tries的高级数据结构有效地查找 LCP 的方法。我实现了一个 Trie 和一个 Compressed 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 长度的总和（最低公共祖先？）。但我仍然很困惑。我该如何进一步进行？

注意：也有可能我对这个问题的处理方法是错误的，所以请也针对这个问题提出其他方法（考虑时间和空间复杂度）。

链接到类似的未回答问题：

代码和理论参考：

更新1：

根据@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 为重复字符建议的方法，但不满足任何测试用例。

更新2：

根据@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（部分输出），上述实现失败。请提出解决此问题的方法。解决此问题的任何其他方法也可以。

4

2 回答 2

7

你的直觉正朝着正确的方向发展。

基本上，每当您看到子字符串的 LCP 出现问题时，您都应该考虑后缀数据结构，例如后缀树、后缀数组和后缀自动机。后缀树可以说是最强大和最容易处理的，它们在这个问题上工作得很好。

后缀树是一个包含字符串所有后缀的树，每个非分支边链都压缩成一条长边。一个满足所有条件的普通 trie 的问题在于它有 O(N^2) 个节点，所以它需要 O(N^2) 个内存。鉴于您可以通过简单的动态规划在 O(N^2) 时间和空间中预先计算所有足够对的 LCP，如果没有压缩，后缀树就不好。压缩的 trie 占用 O(N) 内存，但如果您使用 O(N^2) 算法构建它（就像您在代码中所做的那样），它仍然无用。您应该使用Ukkonen 算法在 O(N) 时间内以压缩形式直接构建后缀树。学习和实现这个算法绝非易事，也许你会发现网络可视化有帮助。作为最后一个小提示，为了简单起见，我假设在字符串的末尾添加了一个标记字符（例如美元 $），以确保所有叶子都是后缀树中的显式节点。

注意：

  1. 字符串的每个后缀都表示为从根到树中叶子的路径（回忆一下哨兵）。这是1-1的对应。
  2. 字符串的每个子字符串都表示为从根到树中节点的路径（包括“内部”长边的隐式节点），反之亦然。此外，所有相等值的子串都映射到同一路径中。为了了解有多少相等的子串映射到特定的根节点路径，请计算节点下方的子树中有多少叶子。
  3. 为了找到两个子串的LCP，找到它们对应的根节点路径，并取节点的LCA。LCP 是 LCA 顶点的深度。当然，这将是一个物理顶点，有几条边从它向下延伸。

这是主要思想。考虑所有子串对，并将它们分类为具有相同 LCA 顶点的组。换句话说，让我们计算 A[v] := LCA 顶点正好为v的子串对的数量。如果你为每个顶点v计算这个数字，那么剩下的解决问题就是：将每个数字乘以节点的深度并得到总和。此外，数组 A[*] 只占用 O(N) 空间，这意味着我们还没有失去在线性时间内解决整个问题的机会。

回想一下，每个子字符串都是根节点路径。考虑两个节点（代表两个任意子串）和一个顶点v。让我们将根在顶点v的子树称为“v-subtree”。然后：

  • 如果两个节点都在 v-subtree 内，那么它们的 LCA 也在 v-subtree 内。
  • 否则，它们的 LCA 在 v-subtree 之外，因此它可以双向工作。

让我们引入另一个量 B[v] := LCA 顶点在v子树内的子串对的数量。上面的语句显示了一种计算 B[v] 的有效方法：它只是v-subtree 中节点数的平方，因为其中的每一对节点都符合标准。但是，这里应该考虑多重性，因此每个节点必须被计算与对应的子串一样多的次数。

以下是公式：

    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(NC) 时间和空间，其中C是字母表的大小。

于 2019-07-24T06:33:22.490 回答
4

要解决问题，请按如下所示进行。

如果你看图片，尝试 abc我已经尝试了 abc 的所有子字符串。

由于添加了所有子字符串，因此 trie 中的每个节点的 endOfWord 都为 true。

现在开始以 DFS 方式与我一起遍历树：

  1. 总和 = 0，堆栈 = {空}

  2. 我们先相遇a。现在对于 L(A,B)a可以与自身形成 1 对。因此做sum=sum+length，sum现在变成1。现在推送长度，即堆栈中的 1。堆栈 = {1}

  3. 移到b现在。子字符串现在是ab. ablikea可以与自身形成 1 对。因此做sum=sum+length，sum现在变成3。将堆栈内容复制到 stack2。我们得到 1 作为 stack top 。这意味着LCPab为a1。但它们可以形成 L(a,ab) 和 L(ab,a)。所以添加 sum = sum + 2 * stack.top() 。总和变为 3+2 = 5。现在将 stack2 复制回堆栈并推入长度，即 2。堆栈变为 {2,1}。

  4. 移至c。子串是abc. 它将与自身形成 1 对，因此加 3。总和变为 5+3 = 8。将堆栈复制到堆栈 2。在顶部，我们有 2abc个ab。将给 LCP 2，它们将形成 2 对。所以总和 = 总和 + 2 * 2。总和变为 12。弹出 2。堆栈现在有 1。abc并且a有 LCP 1 并且可以形成 2 对。因此，总和变为 12+2 = 14。将 stack2 复制回堆栈并将长度（即 3）推入堆栈。

  5. 我们到达了 trie 的尽头。清除堆栈并从b长度 1 开始并继续如上。总和在这里变成 14+1 = 15

  6. 我们到达c. 子字符串在bc这里。总和将变为 15 + 2 + 2*1(top) = 19。

  7. 我们到达了 trie 的尽头。从c长度 1 开始。现在 Sum = 19+1 = 20。

时间复杂度：O(N^3)。因为生成子字符串需要 O(N^2) 时间，将它们插入 trie 需要 O(N) 时间。节点创建是恒定的时间。由于所有子串的长度都不是 N，所以它需要少于 N^3 但 TC 将是 O(N^3)。

我已经测试了这种方法，它只为具有不同字符的单词提供正确的输出。

对于允许重复字符的单词，它会失败。为了解决允许字符重复的单词，您需要为 L(A,B) 存储有关单词在位置 A 和 B 出现的次数的信息。在堆栈中，我们需要推送长度和 B_count 对。然后，您可以使用 length(in stack)*B_count(in stack)*A_count of current substring 找到 LCP 的总和。我不知道有什么方法可以在不使用 4 个循环的情况下找到 A、B 计数。

请参阅下面的图片以了解单词abb

图 1 图 2 图 3

就这样。谢谢你。

于 2019-07-19T22:23:06.703 回答