字元串查找問題，這個情況如何用最短的時間找到最長元素在S1中的位置？
給定字元串S1和目標字元串S2，len(S1)遠大於len(S2)。
定義集合 T(S2) 為 S2 的全部正序子串，例如："xyz" 對應的集合為{x,y,z,xy,yz,xyz} 。
已知，S1至少包含T(S2)中的一個元素，如何用最短的時間找到最長元素在S1中的位置。
示例：S1="abxuyz"，S2="xyz"，i(yz)=4
-------之前理解題目錯誤，所以刪除了代碼..........
這大概和正則表達式沒什麼關係。。是老生常談的dp問題
總之先new一個int[s1.length+1][s2.length+1]
再加一點細節
就完事了
更新回復一下
@掀紗窺君顏
太長不看：樓主的代碼答非所問
代碼效率就不說了，沒有意義
自學了2個小時perl給題主回復一下
為什麼結果是24而不是前不是後？
if ($temp=length $_)&>$len
也就是說，題主給出的答案是s1中最長的由s2子串構成的字元串的位置的結果，答非所問
這是我java的代碼及結果集
String str1 = "ykhkjhkjuioqiwrjxyzasdlkxyzxxxxxxyzzzzysjdfkljuweiqwuoexyzjklajs";
String str3 = "[xyz]*";
Pattern pattern = Pattern.compile(str3);
Matcher matcher = pattern.matcher(str1);
while (matcher.find()) {
System.out.println("匹配結果起點："+matcher.start());
System.out.println(matcher.group(0));
System.out.println("匹配結果終點："+matcher.end());
}
長代碼預警
結果集
匹配結果起點：0
y
匹配結果終點：1
匹配結果起點：1
匹配結果終點：1
匹配結果起點：2
匹配結果終點：2
匹配結果起點：3
匹配結果終點：3
匹配結果起點：4
匹配結果終點：4
匹配結果起點：5
匹配結果終點：5
匹配結果起點：6
匹配結果終點：6
匹配結果起點：7
匹配結果終點：7
匹配結果起點：8
匹配結果終點：8
匹配結果起點：9
匹配結果終點：9
匹配結果起點：10
匹配結果終點：10
匹配結果起點：11
匹配結果終點：11
匹配結果起點：12
匹配結果終點：12
匹配結果起點：13
匹配結果終點：13
匹配結果起點：14
匹配結果終點：14
匹配結果起點：15
匹配結果終點：15
匹配結果起點：16
xyz
匹配結果終點：19
匹配結果起點：19
匹配結果終點：19
匹配結果起點：20
匹配結果終點：20
匹配結果起點：21
匹配結果終點：21
匹配結果起點：22
匹配結果終點：22
匹配結果起點：23
匹配結果終點：23
匹配結果起點：24
xyzxxxxxxyzzzzy
匹配結果終點：39
匹配結果起點：39
匹配結果終點：39
匹配結果起點：40
匹配結果終點：40
匹配結果起點：41
匹配結果終點：41
匹配結果起點：42
匹配結果終點：42
匹配結果起點：43
匹配結果終點：43
匹配結果起點：44
匹配結果終點：44
匹配結果起點：45
匹配結果終點：45
匹配結果起點：46
匹配結果終點：46
匹配結果起點：47
匹配結果終點：47
匹配結果起點：48
匹配結果終點：48
匹配結果起點：49
匹配結果終點：49
匹配結果起點：50
匹配結果終點：50
匹配結果起點：51
匹配結果終點：51
匹配結果起點：52
匹配結果終點：52
匹配結果起點：53
匹配結果終點：53
匹配結果起點：54
匹配結果終點：54
匹配結果起點：55
xyz
匹配結果終點：58
匹配結果起點：58
匹配結果終點：58
匹配結果起點：59
匹配結果終點：59
匹配結果起點：60
匹配結果終點：60
匹配結果起點：61
匹配結果終點：61
匹配結果起點：62
匹配結果終點：62
匹配結果起點：63
匹配結果終點：63
匹配結果起點：64
匹配結果終點：64
關鍵詞：最長公共子串，後綴自動機，O(n)
這個問題是 - 最長公共子串問題
https://zh.wikipedia.org/wiki/%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E4%B8%B2?zh.wikipedia.org
二維dp就可以解決。先求出 最長公共子串 的長度，然後在二維dp數組中反推回去找最長公共子串的開始位置。演算法複雜度和空間複雜度是O(N^2)。
像個面試題，還是我不會的那種。
以一個做題的角度看的做法
S1跑一個SAM出來，然後S2進去搜，因為SAM節點數是O(len(S1))的，所以複雜度不會超過O(len(S1)*len(S2))，隨機情況下效果應該好一些
把S1和所有S2拼一塊，中間加些別的字元建個SA，求一下每個S2的後綴和最近的S1的後綴的lcp
推薦閱讀：
