我想撰寫一個程式，將 2 個字串作為輸入，s1 和 s2，并確定 s1 的哪些字符不能成為 2 的非連續子字串的一部分。因此在輸入
123625421454為 s1 和254s2 之后，程式將output
0 1 0 0 1 1 1 1 0 1 1 1，其中 1 表示字符可以是子字串的一部分，而 0 表示不能。
這個問題真的讓我很惱火，因為我找不到任何演算法可以在沒有非常長的執行時間的情況下找到非連續序列。是否有一個好的解決方案，O 小于或等于 O(N)？我曾嘗試使用哈希和動態編程，但我使用的演算法都不適用于這種情況。
編輯：澄清一下，這個想法是您可以洗掉 s1 的 x 個元素（x 可以是 0）并獲得 s2。在任何情況下都不能成為 s2 一部分的元素應標記為 0，而那些可以的元素應標記為 1。希望這會有所幫助。
uj5u.com熱心網友回復：
一個關鍵的觀察是，如果你到達一個長度為 k 的子子串前綴到一個位置，那么你可以有一個任何長度小于 k 到那個位置的子子串，只需跳過一些尾部元素。同樣適用于后綴。這聽起來可能微不足道，但它引出了解決方案。
所以你想最大化前面的前綴和尾部的后綴。基本上，這意味著您s1從正面訪問一次，從背面訪問一次（使用 reverse s2）。在這兩種情況下，您都希望在每個點都最大化子字串，因此s2只要有可能，您就可以簡單地向前推進。這為您提供了兩個size_t值陣列：給定點的最長可能前綴和后綴。如果這些的總和 >= 的長度s2，則意味著可以連接這些，結果是1；否則這些不能連接，結果是0。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/535754.html
標籤：C 表现散列子串动态规划