华丽地处理字符串

后缀数组 

将A和B拼接后，累计分属两者的后缀对应的LCP-K+1即为答案，但穷举不是个好主意。

如果能快速求出任意两个后缀的最长公共前缀的话，利用类似尺取法的技巧就可以在线性时间统计一段区间了。

而任意两个后缀的最长公共前缀为该区间的LCP值的最小值。

在扫描一段LCA>=K的区域中，如果使用单调栈维护LCP，维护栈顶使LCP最小，就可以快速得到任意爬取区域的最长公共前缀。在“尺取法”爬取的过程中，更新出栈的元素对贡献值的影响，累积到答案中即可。

  

   

    

     

    
    

     
    #include <iostream>
     
    
   

    

     

    
    

     
    #include <string>
     
    
   

    

     

    
    

     
    #include <algorithm>
     
    
   

    

     

    
    

     
     
     
    
   

    

     

    
    

     
    const int MAX_L = 100000 + 1;
     
    
   

    

     

    
    

     
    const int MAX_N = 2 * MAX_L + 1;
     
    
   

    

     

    
    

     

          std::string S;
     
    
   

    

     

    
    

     
    int n, k;
     
    
   

    

     

    
    

     
    int sa[MAX_N + 1], lcp[MAX_N + 1];  // sa[i] := 字典序为i的后缀的起始下标；lcp[i] := S[sa[i]...]与S[sa[i+1]...]的最长公共前缀长度
     
    
   

    

     

    
    

     
    int rank[MAX_N + 1], tmp[MAX_N + 1];
     
    
   

    

     

    
    

     
     
     
    
   

    

     

    
    

     

          /
     
    
  
 

文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。

原文链接：aaaedu.blog.csdn.net/article/details/105133546