如何查找字符串的句點

我從用戶及其具有特定子字符串的字符串中獲取輸入，該字符串通過字符串重複自身。我需要輸出子字符串或其長度AKA期間。如何查找字符串的句點

說

S1 = AAAA // substring is A 
S2 = ABAB // Substring is AB 
S3 = ABCAB // Substring is ABC 
S4 = EFIEFI // Substring is EFI

我可以用一個單個字符開始，並檢查它是否是同它的下一個字符，如果不是的話，我可以用兩個字做，然後有三個等。這將是一個O（N^2）算法。我想知道是否有更優雅的解決方案。

來源

2014-01-16 Aditya

爲什麼S2 substring不是AB？ – csmckelvey

對不起AB。錯字。 – Aditya

現在我對S3感到困惑。美國廣播公司不重複，或者這也是一個錯字？抱歉挑剔，我只是想弄清楚你想要輸出什麼。 – csmckelvey

您可以通過感應計算字符串的每個前綴的週期，以線性時間和恆定的額外空間完成此操作。我不記得細節（有幾件事情可以正確），但你可以在Crochemore和Rytter的「文本算法」的第13.6節中找到它們。（你可以在Maxime Crochemore的網站上免費找到這本書的pdf副本！）

來源

2014-01-16 19:44:59 tmyklebu

+1以供參考。算法真的就在那裏，第340頁。雖然看起來不像採訪解決方案:) –

對勘誤列表的引用也有幫助，因爲子例程'Next_MS'中至少有三個錯誤，並且至少還有兩個錯誤在'Per'中。 –

那麼，如果輸入字符串中的每個字符都是重複子字符串的一部分，那麼您只需存儲第一個字符並將其與字符串的其餘字符逐個比較即可。如果你找到一個匹配，字符串，直到匹配一個是你的重複字符串。

來源

2014-01-16 18:02:37

你能展示一個代碼示例，說明這對於幾個輸入是如何工作的嗎？ – csmckelvey

夥計。閱讀我的問題示例下面的文本段落：| – Aditya

哦，我沒有看到。但是既然你說它必須包含一個循環，那麼這個方法的複雜度就是O（N），因爲你只是在最壞的情況下比較第一個字符和整個字符串。@csmckelvey僞代碼將如下所示： 'char first = input [0]; String repeatingString = first; int i = 1; char nextChar = input [i]; while（first！= nextChar） { repeatingString + = nextChar; i ++; nextChar = input [i]; } ' –

您可以在線性時間內爲整個字符串構建一個後綴樹（後綴樹很容易在線查找），然後遞歸計算並存儲後綴樹葉的數量（後綴前綴的出現次數）N（v ）在後綴樹的每個內部節點v的下面。還遞歸地計算並存儲樹的每個節點處的每個後綴前綴L（v）的長度。然後，在樹中的內部節點v處，在v處編碼的後綴前綴是一個重複子序列，如果N（v）等於字符串被L（v）除的總長度，那麼它將生成您的字符串。

來源

2014-01-16 18:14:29 user2566092

你當然可以用後綴樹來做到這一點，但這比做KMP預處理要慢幾個數量級。 – tmyklebu

@tmyklebu你如何看待後綴樹的常量比其他算法大幾個數量級？這意味着像常量1000.一個後綴樹當然沒有隱藏常量爲1000. – user2566092

我沒有看到實際沒有。歡迎您將我鏈接到您最喜歡的實現，我可以比較一下我參考的線性時間，恆定空間算法的一個很好的實現，但後綴樹慢1000倍並不會讓我感到意外。 – tmyklebu

讓我假定字符串n的長度至少比期間p大兩倍。

算法

讓m = 1，並且S整個字符串
取m = M * 2
- 查找子串S的下一個出現[：米]
- 讓k成爲下一次出現的開始
- 檢查是否S [：k]爲週期
- 如果不去2.

例

假設我們有一個字符串

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC

對於每個功率m 2我們發現第一個2^m字符的重複。然後我們將這個序列擴展到第二個事件。我們從2^1開始，所以CD。

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCD CDCD CDCD CDCD CD

我們不會延長CD，因爲下一次出現就在此之後。然而CD不是我們正在尋找的子字符串，所以讓我們來看下一個功能：2^2 = 4和子字符串CDCD。

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCD CDCD

現在讓我們將字符串擴展到第一個重複。我們得到

CDCDFBF

我們檢查這是否是週期性的。這不是我們走得更遠。我們嘗試2^3 = 8，所以CDCDFBFC

CDCDFBFCDCDFDFCDCDFBFCDCDFDFCDC 
CDCDFBFC  CDCDFBFC

我們儘量延長，我們得到

CDCDFBFCDCDFDF

，這確實是我們的時間。

我希望這可以在O（n log n）中用一些類似KMP的算法來檢查給定字符串出現的位置。請注意，一些邊緣情況仍應在此處制定。

直覺上這應該可行，但我的直覺已經在這個問題上一次失敗了，所以請糾正我，如果我錯了。我會試着找出一個證明。

雖然是一個非常不錯的問題。

來源

2014-01-16 19:30:51

KMP預處理的要點是它計算後綴前綴匹配。您可以從故障表的最後一個條目中讀取字符串的時間段。 – tmyklebu

那麼，在這裏，我的意思是KMP作爲O（n）算法來查找字符串中的模式。 –

如何查找字符串的句點

回答

相關問題