后綴數組 

將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];/

總結

以上是生活随笔為你收集整理的华丽地处理字符串的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。