假設陣列 B 是通過將陣列 A 與自身連接 n 次而構成的（例如：A=[1,2,3], n=3, B=[1,2,3,1,2,3,1 ,2,3]) 通過給定的 B（我們不知道 n）找到 A 的有效演算法是什么？UPD我們搜索最小的A（當B=[1,2,1,2,1,2,1,2]時，A=[1,2]，而不是[1,2,1,2]）
uj5u.com熱心網友回復：
例如，假設[1,2,1,2,1,2,1,2]平均值n是 4 而不是 2。換句話說，您假設最小的此類子串列 A。否則，可能有多種解決方案。
列舉 B 的長度的唯一整數除數（包括 1）。這些將是
n.對于每個除數，從最小的開始，將其視為 的候選值
n：一個。取
len(B)/nB的第一個元素并開始檢查它是??否是一個通過 B 重復的子串列（我假設您可以找到一種有效的方法。如果您需要，我可以添加建議。）灣 如果
n有效（您到達 B 的末尾并且所有內容都匹配），那么您就完成了，否則，嘗試下一個除數
uj5u.com熱心網友回復：
您基本上可以找到最長的前綴B也是后綴。您可以從KMP pattern matching演算法中涉及的步驟中匯出該表。
請注意，可能有多個正確的解決方案。（比如1,2,1,2,1,2,1,2可能有Aas1,2,1,2或1,2.
找到后，您將需要針對 的切片重新運行匹配，B以確保整個陣列B與重復模式匹配。這是必要的，因為有可能是邊緣的情況下，如1,2,1,2,3,4,1,2,1,2其中有1,2,1,2作為，這也是一個后綴的最長前綴，但它不是連續重復A。
如果獲得的長度不能B均勻地劃分長度，則每次都需要均勻地減小長度（如因子方式）以查看哪個匹配。（示例：）1,2,1,2,1,2。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/387594.html
標籤：算法
下一篇：有效計數范圍內的出現次數