1+ package Algorithms .string ;
2+
3+ import java .util .ArrayList ;
4+ import java .util .HashMap ;
5+ import java .util .List ;
6+
7+ public class FindSubstring {
8+ public static void main (String []strs ) {
9+ String []L = {"fooo" ,"barr" ,"wing" ,"ding" ,"wing" };
10+
11+ System .out .println (findSubstring ("lingmindraboofooowingdingbarrwingmonkeypoundcake" ,L ));
12+ }
13+
14+ public static List <Integer >findSubstring (String S ,String []L ) {
15+ HashMap <String ,Integer >map =new HashMap <String ,Integer >();
16+ HashMap <String ,Integer >found =new HashMap <String ,Integer >();
17+ List <Integer >ret =new ArrayList <Integer >();
18+
19+ if (S ==null ||L ==null ||L .length ==0 ) {
20+ return ret ;
21+ }
22+
23+ int cntL =0 ;
24+
25+ // put all the strings into the map.
26+ for (String s :L ) {
27+ if (map .containsKey (s )) {
28+ map .put (s ,map .get (s ) +1 );
29+ }else {
30+ map .put (s ,1 );
31+ cntL ++;
32+ }
33+ }
34+
35+ int lenL =L [0 ].length ();
36+
37+ int cntFound =0 ;
38+
39+ // 注意这里的条件：i < S.length() - lenL * L.length
40+ // 这里很关键，如果长度不够了，不需要再继续查找
41+ for (int i =0 ;i <=S .length () -lenL *L .length ;i ++) {
42+ // clear the found hashmap.
43+ found .clear ();
44+ cntFound =0 ;
45+
46+ // 一次前进一个L的length.
47+ // 注意j <= S.length() - lenL; 防止越界
48+ for (int j =i ;j <=S .length () -lenL ;j +=lenL ) {
49+ String sub =S .substring (j ,j +lenL );
50+ if (map .containsKey (sub )) {
51+ if (found .containsKey (sub )) {
52+ if (found .get (sub ) ==map .get (sub )) {
53+ // 超过了限制数目
54+ break ;
55+ }
56+
57+ found .put (sub ,found .get (sub ) +1 );
58+ }else {
59+ found .put (sub ,1 );
60+ }
61+
62+ if (found .get (sub ) ==map .get (sub )) {
63+ cntFound ++;
64+ }
65+
66+ // L中所有的字符串都已经找到了。
67+ if (cntFound ==cntL ) {
68+ ret .add (i );
69+ }
70+ }else {
71+ // 不符合条件，可以break,i前进到下一个匹配位置
72+ break ;
73+ }
74+ }
75+ }
76+
77+ return ret ;
78+ }
79+ }