檢查子字符串是否存在於字符串的開頭，中間和結尾，但允許交叉點

-1

聽起來很簡單，您可以簡單地迭代並檢查它們，但這裏的問題是優化：不要進行任何不必要的檢查，不需要新的對象或操作。檢查子字符串是否存在於字符串的開頭，中間和結尾，但允許交叉點

該算法將針對大量測試用例進行測試，以驗證其效率。

例子：

"aaaa"包含"aa"開頭，中間和結尾。

"baabaabaaaabbaab"包含"baab"開頭，中間和結尾。看到十字路口。

還有一件事我忘了說：

你沒有給子來檢查，你需要找到，如果這種子存在，如果它不return false，如果它return true。查找滿足這些條件的最長子字符串並將其返回或打印出來（您的選擇）。

一個簡單的布爾函數，對嗎？

更新：

子串需要至少2個字符的短主字符串。

對不起，這是我在「aaa」示例中的錯誤，我解決了它。

來源

2015-10-19 Mr. M

你想要一個特定語言的答案嗎？如果是這樣，那麼可能更新您的標籤。 –

任何語言或僞代碼 –

你知道這種模式嗎？或者你應該找到它？ –

您可以KMP，字符串匹配算法解決這個問題。用它來生成一個數組fail[]

fail[i] = max {k | S[1:k] == S[i-k+1:i]}

然後，你可以列舉的fail[n](fail[n], fail[ fail[n] ], fail[ fail[fail[n]] ] ...)所有可能的值來檢查它是否存在於中間。

複雜度爲O(n)。

來源

2015-10-19 08:08:01 throwit

這是哪一種語言？ –

只是僞代碼，你可以先學KMP – throwit

解決這個問題的一個簡單方法是從一開始就檢查輸入中的所有子字符串。比較每個子字符串以查看它是否存在於最後，然後檢查它是否存在於中間。對於中間檢查，您可以將其第一個和最後一個字符刪除後的輸入字符串進行比較。

public boolean subStrings(String input) { 
    if (input == null || input.equals("")) { 
     return false; 
    } 
    if (input.length() == 1) { 
     System.out.println(input + " is a match!"); 
     return true; 
    } 

    boolean foundIt = false; 
    String longestMatch = ""; 

    for (int i=1; i < inputNew.length(); ++i) { 
     String substring = inputNew.substring(0, i); 
     boolean endMatch = inputNew.substring(inputNew.length()-i, inputNew.length()).equals(substring); 
     boolean midMatch = inputNew.substring(1, inputNew.length()-1).contains(substring); 
     if (endMatch && midMatch) { 
      longestMatch = substring; 
      foundIt = true; 
     } 
    } 

    if (foundIt) { 
     System.out.println(longestMatch + " is a match!"); 
     return true; 
    } 
    else { 
     return false; 
    } 
} 

subStrings("baabaabaaaabbaab");

輸出：

baab is a match!

來源

2015-10-19 07:55:57

在你的問題中，你告訴我們你希望函數返回true/false，而不是字符串。我假設你想讓我只打印最長的子字符串。 –

是的，但你的代碼中的問題是它依賴蠻力，我想看到它有更好（更快）的方式 –

對不起，你的方法是O（N^2）。你循環大概N次，但是你在每個循環中進行一次字符串搜索。字符串搜索的運行時間是O（N）。 – invisal

這是其中的一個「你可能會在理論複雜性方面顯著較好，但在現實中，線性操作總是快」的答案：

假設in是你輸入的字符串，pattern是你在找什麼for，並且您可以讀取或查找C標準庫樣式的方法，如strncmp。令l_in爲輸入中的字符數，l_pattern爲模式中的字符數。

只需明確檢查開始（strncmp(in,pattern,l_pattern)）;然後用從第二個字母上（strstr(in+1, pattern）沼澤正常線性搜索：

如果strstr沒發現什麼，沒有中間的比賽，也不是結束比賽。
如果它在最後（strstr的結果是l_in-l_pattern），您沒有中間匹配。
如果最後沒有找到它，那麼您的中間匹配。手動檢查（strncmp(in+l_in-l_patter, pattern, l_pattern)）結束比賽。

爲什麼這樣更快？由於現代計算機非常適合線性搜索數據，請參閱Bjarne "C++" Stroustrup's why you should avoid linked lists。簡而言之，讓您的CPU在預取CPU緩存的連續內存上運行要比避免少量重複檢查「聰明」得多。

來源

2015-10-19 08:08:44

我們既不知道模式也不知道它的長度 –

@M先生：代碼中沒有任何地方假設你在開始之前做了什麼 - 'l_pattern = strlen（pattern）'，if你想要僞C。 –

是的，但你沒有提到你給'模式'的值，你首先選擇整個字符串-1或第一個字母。有很多方法。 –

讓我們跳鯊魚：

function the_best_match_at_the_beginning_the_middle_and_the_end(s){ 
    print(s); 
    return true; 
}

來源

2015-10-19 08:17:58 biziclop

我的想法。我希望我可以在我的工作中爲所有單元測試做這件事^^ –

對不起，我的壞，你是對的，它至少需要1個字符或它將是微不足道的。 –

檢查子字符串是否存在於字符串的開頭，中間和結尾，但允許交叉點

回答

相關問題