算法研究之字元串包含

今天看到一道算法題：給定一長一短的倆個字元串A，B，假設A長B短，現在，要你判斷B是否包含在字元串A中。

比如，如果是下面兩個字元串： 

String 1: ABCDEFGHLMNOPQRS 

String 2: DCGSRQPOM 

答案是true，所有在string2裡的字母string1也都有。 

如果是下面兩個字元串： 

String 2: DCGSRQPOZ 

答案是false，因為第二個字元串裡的Z字母不在第一個字元串裡。

我們很容易想到的一個算法就是輪詢，每次取短字元串中的字元在長字元串中找。

方法1：

這種算法複雜度為O(段字元串長度*長字元串長度)

方法2：

這種方法是在方法1的基礎上改進的，我們可以先對兩個字元串進行快速排序，然後再進行輪詢，這樣複雜度就變成O(mlogm)+O(nlogn)+O(m+n)，随着字元串長度的增加，這個算法的優勢就越來越明顯。